skatsuta / vrp-solver Goto Github PK

View Code? Open in Web Editor NEW

85.0 4.0 26.0 9.65 MB

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

License: MIT License

Python 100.00%

vehicle-routing-problem or-tools python

vrp-solver's Introduction

Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) solver

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

Implementation is based on "Vehicle Routing Problem with Time Windows" section in Google OR-Tools documentation.

What's this?

This program solves Capacitated Vehicle Routing Problem with Time Windows (CVRPTW).

For example, given the following network and three vehicles at the depot (Node 0), consider the problem of what route each vehicle should take to pick up all the demands of all the nodes in the shortest possible time.

In this case, this program would give the following solution, for example:

Prerequisites

Python 3.9 or later is required.

Usage

First, install the dependencies:

# Install Graphviz on macOS (On other platforms, use their own package managers)
$ brew install graphviz

# Create a Python virtual environment
$ python -m venv .venv
# Activate the virtualenv
$ source .venv/bin/activate
# Install the dependencies
$ pip install -r requirements.txt

Alternatively, if you have Poetry installed, run the following commands instead of the second to fourth line above:

$ poetry install
$ poetry shell

Then, let's solve an example!

$ python solver.py data.example.yaml

It should output the following solution:

Route for vehicle 0:
     [Node  0: Load( 0) Time( 0,   0)]
  -> [Node  9: Load( 0) Time( 2,   5)]
  -> [Node  8: Load( 1) Time(10,  13)]
  -> [Node  5: Load( 2) Time(17,  20)]
  -> [Node  4: Load( 4) Time(35,  55)]
  -> [Node  3: Load( 7) Time(60,  67)]
  -> [Node  1: Load( 9) Time(68,  75)]
  -> [Node  0: Load(10) Time(79, 100)]
Load of the route: 10
Time of the route: 79 min

Route for vehicle 1:
     [Node  0: Load( 0) Time( 0,   8)]
  -> [Node  7: Load( 0) Time( 2,  10)]
  -> [Node 13: Load( 3) Time(15,  18)]
  -> [Node 12: Load( 6) Time(22,  25)]
  -> [Node 15: Load( 8) Time(45,  65)]
  -> [Node 11: Load( 9) Time(85,  89)]
  -> [Node  0: Load(10) Time(96, 100)]
Load of the route: 10
Time of the route: 96 min

Route for vehicle 2:
     [Node  0: Load( 0) Time( 0,  25)]
  -> [Node 14: Load( 0) Time(10,  30)]
  -> [Node 16: Load( 3) Time(30,  50)]
  -> [Node  6: Load( 4) Time(55,  72)]
  -> [Node  2: Load( 7) Time(75,  80)]
  -> [Node 10: Load( 8) Time(84,  89)]
  -> [Node  0: Load(10) Time(95, 100)]
Load of the route: 10
Time of the route: 95 min

Total time of all routes: 270 min

In addition, if you want to export images of the network and routes, you can specify filenames for them using -n/--export-network-graph and -r/--export-route-graph options:

$ python solver.py data.example.yaml \
    --export-network-graph network.png \
    --export-route-graph route.png

Then the program saves the network image to network.png and the route image to route.png for vizualizing the network and vehicle routes.

File format is automatically determined by the file extension; see https://graphviz.org/docs/outputs/ for the supported file formats. For example, if you pass --export-network-graph network.svg, the file will be the SVG format.

data.example.yaml is just example data created for a dummy problem, so if you have your own problem to solve, copy this file, create your own data.yaml and pass it to the program! 💪

$ python solver.py data.yaml

vrp-solver's People

Contributors

Stargazers

Watchers

vrp-solver's Issues

Visit within hours slot

Hi,
thanks for this great example. It is really helpful.
I want to ask some thing
How can we handle this scenario
I have 2525 Distance Matrix and 2525 Time Matrix (In seconds)
My time window is to visit depot from 9:00 and visit every Location within given time slot given

10:00 to 11:00
12:00 to 13:00

and so on up to 18:00 (9:00 to 18:00) and 1 hour slot of visit.
I have tried this program and set max time limit to 64800 but solution remains null
number of vehicles are 4

Time and Distance matrix for better understand is
Distance

[[0,11231,31164,29866,45009,35010,30030,99218,38362,27344,29097,37192,27223,27469,31970,35267,27944,38915,22981,6260,22638,97339,22668,29408,25590],[11448,0,27868,26570,13648,31715,29574,108318,35067,21466,25801,31780,23927,21592,28162,31971,24649,35620,19686,11712,19342,35674,19372,28952,22294],[33622,29340,0,9348,28957,6920,9957,24133,9836,11672,8778,4354,9515,12575,8060,3807,6998,6926,11282,29263,13241,8234,10566,13339,11863],[29419,26668,8748,0,28482,13301,6687,32329,18032,11364,1411,8539,1445,12266,2141,10381,2803,14555,11391,25060,12220,17932,6743,9358,2967],[46524,14296,27244,27695,0,27530,29569,85361,34622,18024,26926,29996,26236,18150,29287,30608,25773,33079,17825,19711,16154,35229,20308,28947,23419],[34687,31155,7514,13677,28842,0,17040,22737,8441,10936,13107,11106,13845,11544,12697,11036,11327,7593,11978,31010,13136,9551,12955,41128,16192],[30485,29615,11121,7231,30345,16914,0,38611,35771,17793,7830,7419,8381,18696,5466,9261,9171,31895,22064,24134,23385,16812,21728,3658,11527],[54313,107239,25210,33392,84001,26370,39672,0,18680,34040,32821,30159,33559,34942,44243,27947,31041,19965,32724,61049,34683,25713,32008,40573,48441],[38694,35163,9591,17773,35645,10752,35042,17552,0,18421,17203,14540,17940,19323,16793,12456,15423,4473,17105,35017,19065,9705,16389,35943,20288],[27473,21070,11426,11867,18330,11378,17553,32071,17775,0,10605,14179,10420,914,13007,14790,9422,16927,4765,23797,5125,18885,5469,25834,12007],[27467,24716,7978,1354,26530,12189,7446,31216,16920,10251,0,7968,909,11153,2900,9810,2034,13786,9439,23108,10268,17361,5606,10116,3373],[33273,30522,4596,8389,32336,10127,7419,27051,13024,13746,7973,0,8711,14648,5547,3539,6649,8993,15245,31277,16074,9512,14910,10800,10781],[27405,24654,8646,1386,26469,12861,7706,31888,17592,10923,639,8561,0,11825,3160,10404,2628,14454,9377,23047,10206,17954,5409,10376,2845],[27907,21148,12192,12301,18408,11461,17987,32154,17858,878,11039,14945,10854,0,13441,15556,9856,17010,5199,24230,5203,18968,5903,26268,12441],[32437,28343,8013,2405,30158,13123,5186,42676,16819,12967,3004,6222,3555,13870,0,8411,4345,13569,13066,26086,13896,15962,8565,7726,4797],[35245,32494,4919,10617,34308,10450,9647,26181,12154,15203,10201,4172,10939,16105,8389,0,8621,8123,17217,30886,18046,8547,12742,13028,13009],[26887,24136,6251,2653,25950,11162,8677,29116,14820,9225,1884,7685,2524,10127,4131,7876,0,12059,8859,22528,9688,13367,8524,11348,5128],[39536,36005,7342,15853,36487,7856,30932,18569,4542,19263,15283,9300,16021,20165,13136,8295,13503,0,17947,52309,19906,2962,17231,31833,18368],[23064,19533,11250,11324,19812,12021,22047,32167,17871,4836,10555,16533,7375,5959,12916,14471,9402,18423,0,19387,1812,18477,2099,21425,7598],[6464,11639,28736,24960,45667,31249,24141,59372,34601,23582,24191,31302,23501,23708,26081,33145,23039,52656,19220,0,18876,50850,18906,23519,20374],[22877,19346,12720,12410,17025,13491,23700,33637,19341,5205,11640,17619,8107,5331,14002,15941,10488,19893,1889,19200,0,19947,3896,23078,8683],[56788,55918,7749,16260,39274,10643,29060,24123,7329,22050,15690,12713,16427,22952,16058,8632,13910,3284,20734,50437,22694,0,20018,29961,37829],[23416,19885,8855,6646,21501,11324,13000,30351,16054,5549,5599,11075,5312,6451,8453,11687,5373,16607,1952,19739,3501,16661,0,21801,6184],[30745,29875,14095,9552,30605,19888,3231,38462,35622,20490,10526,10392,10702,28291,9103,12235,11868,31746,22324,24394,23645,29940,21988,0,9156],[24132,22882,11047,2906,24697,15154,8499,45284,19885,12075,3114,11036,2797,13198,4550,12879,5103,16854,7231,21619,8060,20429,6179,9431,0]]

Time

[[0,1159,3444,2596,2148,3778,2325,4589,3992,2660,2450,3435,2503,2652,2633,3870,2302,4141,1721,755,1784,4160,1646,2273,2363],[1245,0,3681,2833,1644,4015,2818,4549,4229,2634,2687,3818,2740,2626,3064,4107,2539,4378,1957,1355,2021,4848,1883,2766,2599],[3399,3603,0,1724,3910,1474,1697,2478,1463,2198,1607,940,1742,2329,1639,695,1385,1260,2092,3143,2391,1435,1946,2163,2144],[2598,2858,1822,0,3353,2532,1030,3766,2750,2034,274,1590,299,2165,385,2094,527,2842,1529,2342,1813,2983,1295,1254,524],[2317,1670,3660,3243,0,3649,3586,4290,4242,1845,3097,4085,3088,1837,3474,4196,2949,4439,2040,2658,1690,4862,2342,3534,3009],[3712,3931,1444,2559,3866,0,3051,2045,1029,2131,2442,2274,2577,2258,2593,2149,2219,1148,2216,3750,2425,1584,2320,3142,2979],[2342,2769,1950,1114,3456,3012,0,2983,2638,2987,1229,1176,1317,3117,867,1686,1469,2449,2184,1983,2382,2575,2128,525,1247],[4850,4658,2539,3705,4445,2621,2886,0,1488,3711,3588,3365,3723,3841,3692,2940,3365,1648,3558,4521,3857,2010,3412,3064,3786],[3801,4020,1491,2656,4310,1572,2444,1525,0,2662,2539,2317,2674,2793,2691,1932,2317,640,2509,3838,2808,1074,2363,2622,3076],[2429,2619,2294,2121,1850,2130,2928,3817,2802,0,1940,2719,2055,168,2283,2831,1682,2920,932,2466,973,3357,1100,2946,2105],[2384,2644,1715,287,3140,2433,1206,3666,2651,1935,0,1501,193,2066,561,2006,421,2735,1316,2129,1600,2895,1116,1430,619],[3300,3560,1098,1520,4056,2186,1124,3007,2017,2665,1436,0,1570,2795,1139,706,1286,1634,2232,3048,2516,1770,2175,1590,1944],[2318,2577,1765,264,3073,2438,1229,3671,2656,1940,147,1601,0,2071,585,2106,520,2785,1249,2062,1533,2995,1035,1453,499],[2518,2618,2406,2211,1849,2178,3018,3865,2850,177,2030,2831,2144,0,2373,2942,1771,2968,1022,2556,973,3404,1190,3036,2194],[2813,3103,1630,422,3599,2661,829,3721,2761,2295,538,1300,626,2426,0,1788,778,2578,1775,2454,2059,2677,1627,1290,846],[3824,4084,1096,2023,4580,2184,1633,2849,1859,2908,1938,1022,2073,3039,1731,0,1810,1476,2755,3568,3040,1447,2672,2100,2447],[2135,2395,1406,536,2891,2155,1369,3414,2399,1657,390,1473,498,1788,724,1761,0,2425,1067,1880,1351,2601,1010,1592,881],[4022,4241,1335,2809,4531,1219,2209,1649,659,2883,2692,1946,2827,3014,2658,1542,2469,0,2730,3844,3029,631,2584,2386,3229],[1607,1826,2061,1460,2085,2057,2177,3573,2558,921,1315,2446,1320,1065,1692,2612,1166,2708,0,1644,373,3178,444,2125,1283],[755,1299,3328,2410,2425,3745,2079,4581,3958,2626,2264,3189,2255,2618,2387,3699,2116,4047,1687,0,1751,4052,1612,2027,2159],[1731,1950,2407,1759,1780,2403,2422,3920,2904,934,1613,2745,1616,926,1990,2958,1465,3054,429,1768,0,3524,764,2370,1582],[4162,4589,1584,3058,4891,1579,2168,1932,1019,3243,2941,2125,3076,3374,2723,1412,2719,598,3091,3803,3390,0,2944,2345,3067],[1771,1990,1920,1313,2509,2250,2281,3484,2468,1114,1131,2445,1062,1245,1637,2557,1062,2618,418,1808,798,3088,0,2286,1252],[2445,2872,2356,1294,3559,3419,473,2974,2630,3189,1432,1582,1498,3353,1171,2092,1672,2440,2287,2086,2485,2445,2231,0,1423],[2500,2713,2242,532,3209,2934,1266,3865,3152,2274,581,2028,512,2418,873,2533,948,3262,1352,2110,1636,3422,1253,1311,0]]

as a sample Time Window

            { 9*3600, 9*3600 },   // depot
            { 10 * 3600, 11 * 3600 }, // 1
            { 11 * 3600, 12 * 3600 }, // 2
            { 10 * 3600, 11 * 3600 }, // 3
            { 12 * 3600, 13 * 3600 }, // 4
            { 14 * 3600, 18 * 3600 }, // 5
            { 15 * 3600, 16 * 3600 }, // 6
            { 17 * 3600, 18 * 3600 }, // 7
            { 9 * 3600, 10 * 3600 },  // 8
            { 11 * 3600, 14 * 3600 }, // 9
            { 12 * 3600, 15 * 3600 }, // 10
            { 9 * 3600, 12 * 3600 },  // 11
            { 16 * 3600, 17 * 3600 }, // 12
            { 17 * 3600, 18 * 3600 }, // 13
            { 10 * 3600, 13 * 3600 }, // 14
            { 11 * 3600, 12 * 3600 }, // 15
            { 15 * 3600, 16 * 3600 }, // 16
            { 16 * 3600, 17 * 3600 }, // 17
            { 15 * 3600, 18 * 3600 }, // 18
            { 14 * 3600, 17 * 3600 }, // 19
            { 12 * 3600, 13 * 3600 }, // 20
            { 11 * 3600, 12 * 3600 }, // 21
            { 13 * 3600, 14 * 3600 }, // 22
            { 15 * 3600, 16 * 3600 }, // 23
            { 17 * 3600, 18 * 3600 }, // 24

if I change max_time to 86400 it gives me solution. but I don't need that.
I will be very glad if you can help me with it.
Thanks

add feature into time window

Hi, thank you for this great experience sharing. It's a really promising repository for future projects.

I want to tell you about my specific feature.

As you know we have some time windows to visit clients. I need extra control for the back to depot before it closes.

So depots are open between 08:00 and 18:00 so vehicles have to back to their depots before close.

Do you know how can we add this feature into the time window?

Thanks

it is mapping vehicles for node with zero requirement

respected skatsuta,

I tried giving demand zero for all the nodes still it is mapping vehicles to those nodes how can I prevent it from mapping any vehicle to the node with 0 demand. kindly help me it will be of great help

Load of data error

Hi Skatsuta,

While running your code, I'm facing some error by loading the dataset. Could you please help me with that.

Error:
usage: solver.py [-h] [-g] [--gls] [-v] path
solver.py: error: the following arguments are required: path

Thanks in advance!

Getting an error when running it on pycharm

I'm trying to run the model on pycharm with the data from the test problem but I get the following output

Any help would be greatly appreciated as i'm currently working on a school project

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.