Vehicle routing problems in python

Solving Single Depot Capacitated Vehicle Routing Problem Using Column Generation with Python

Vehicle routing problem (VRP) is identifying the optimal set of routes for a set of vehicles to travel in order to deliver to a given set of customers. When vehicles have limited carrying capacity and customers have time windows within which the deliveries must be made, problem becomes capacitated vehicle routing problem with time windows (CVRPTW). In this post, we will discuss how to tackle CVRPTW to get a fast and robust solution using column generation.

Problem

We consider a pizza restaurant chain, PPizza, in the Los Angeles, CA area with 34 stores. Each store operates from 10am to 1am everyday. PPizza offers three pizza sizes (small, medium, large) with various toppings and soft drinks. Pizzas are prepared with fresh ingredients and baked in store on demand.

PPizza forecasts weekly demand of food items for each store and identifies required ingredients and soft drinks. Fresh ingredients are delivered to stores daily from the main depot once a day. Soft drinks are delivered and replenished by suppliers directly.

Figure 1 shows location of stores and the depot. Each store has time windows between 9am and 3pm where delivery needs to be done within. Unloading time varies by store depending on location and parking availability.

Figure 1: PPizza depot and stores

Trucks can leave from the depot at 6am and need to return the depot by 5pm. Each truck can be used once and has a limited capacity of lbs.

Since delivery cost is a function of number of trucks used in delivery, minimizing the total number of trucks used for delivery minimizes total cost. We want to identify the truck operating schedules to be able to deliver fresh ingredients to each store with given time windows by minimizing the total cost (minimizing the number of trucks used).

Analysis

We first formulate the problem as a mixed integer program. Then, we solve the problem for a range of number of available trucks using the formulation. Since CVRPTW is NP-hard, we expect that model run time increases as number of available trucks decreases.

We also develop column generation based algorithm to solve the problem.

Finally, we compare performance of two solution methodologies; mixed integer program and column generation.

General Formulation

We develop a mixed integer model for the PPizza delivery problem as follows.

We solve the mixed integer model using Python with PuLp. The following is the implementation.

In the solution, we deliver with trucks driving total hours (Figure 5). Algorithm run time is less than 2 minutes.

Figure 5: Column generation solution

Figure 6 shows algorithm convergence. Note that subproblem objective reached in iterations.

Figure 6: Column generation algorithm convergence

PPizza Solution

As a result, column generation uses less number of trucks than the general mixed integer formulation.

Figure 7 illustrates solution for PPizza with 12 trucks. Each truck leaves depot at 6am and returns by 5pm.

References

Desrochers, M., Lenstra, J.K., Savelsbergh, M.W.P., Soumis, F. (1988). Vehicle routing with time windows: Optimization and approximation. In: Golden, B.L., Assad, A.A. (Eds.), Vehicle Routing: Methods and Studies. North-Holland, Amsterdam, pp. 65–84.

Updated: December 15, 2019

Share on

You may also enjoy

2019 INFORMS Annual Conference

The 2019 INFORMS Annual Meeting was held at Seattle from October 20 to October 23. There were over 7,000 attendees which was record-breaking.

Predicting Short Term Trucking Rates with Random Forests

In this post, we present a random forest model to predict short term trucking rates using Python.

Visualizing Network Optimization Model Results Using Python

A quick way to validate network optimization model results is visually creating optimal flows map which shows flows between source and destination. This pos.

Weighted Clustering with Minimum-Maximum Cluster Sizes, Greenfield Analysis

This post provides a center of gravity based algorithm for a greenfield analysis. Algorithm is based on k-means clustering enhanced with optimization.

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

vehicle-routing-problem

Here are 85 public repositories matching this topic.

iRB-Lab / py-ga-VRPTW

A Python Implementation of a Genetic Algorithm-based Solution to Vehicle Routing Problem with Time Windows

hubbs5 / or-gym

Environments for OR and RL Research

N-Wouda / ALNS

Adaptive large neighbourhood search (and more!) in Python.

yorak / VeRyPy

A python library with implementations of 15 classical heuristics for the capacitated vehicle routing problem.

dungtran209 / Modelling-and-Analysis-of-a-Vehicle-Routing-Problem-with-Time-Windows-in-Freight-Delivery

A MSc’s Dissertation Project which focuses on Vehicle Routing Problem with Time Windows (VRPTW), using both exact method and heuristic approach (General Variable Neighbourhood Search)

skatsuta / vrp-solver

Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) solver written in Python.

shlok57 / VehicleRoutingProblem

Solved using AI techniques: Savings, Sweep, Genetic Algorithm, Google OR Tools

PyVRP / PyVRP

Open-source, state-of-the-art VRP solver.

jonzhaocn / VRPTW-ACO-python

A python implementation of a ant colony optimization based solution to Vehicle Routing Problem with Time Windows.

ahottung / NLNS

Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem

shayan-ys / VRPTW-ga

Vehicle Routing Problem with Time Windows — Genetic Algorithm solution with Python

sudhan-bhattarai / CVRPTW_MILP

Solving a Capacitated Vehicle Routing Problem with time windows constraints (CVRPTW) with Mixed Integer Linear Programming (MILP) in python-gurobi API.

leonlan / VRPLIB

Python library for working with vehicle routing problem instances.

krishna-praveen / Capacitated-Vehicle-Routing-Problem

Capacitated vehicle routing problem implemented in python using DEAP package. Non dominated sorting Genetic algorithm is used to solve Multiobjective problem of minimizing Total distance travelled by all vehicles and minimizing total number of vehicles at same time.

chenmingxiang110 / tsp_solver

Solving tsp (travel sales problem) using ruin & recreate method.

theosotr / tabu_search-vrpcd

A Tabu Search algorithm for the Vehicle Routing Problem with Cross-Docking.

lstolcman / HMO-project

Solver for Capacitance Vehicle Routing Problem — School bus routing problem with bus stop selection

mahdims / Branch-and-price-

This is my implementation of a branch and price algorithm to solve the humanitarian aid distribution problem. This problem is a VRP with a specific objective function

cbao / Multiple-Vehicle-Routing

yining043 / PDP-N2S

This repo implements our paper, «Efficient Neural Neighborhood Search for Pickup and Delivery Problems», which has been accepted as short oral at IJCAI 2022.

Improve this page

Add a description, image, and links to the vehicle-routing-problem topic page so that developers can more easily learn about it.

Add this topic to your repo

To associate your repository with the vehicle-routing-problem topic, visit your repo’s landing page and select «manage topics.»

Источник