kuifje02 / vrpy

A python framework for solving the VRP and its variants with column generation.

VRPy

VRPy is a python framework for solving Vehicle Routing Problems (VRP) including:

• the Capacitated VRP (CVRP),
• the CVRP with resource constraints,
• the CVRP with time windows (CVRPTW),
• the CVRP with simultaneous distribution and collection (CVRPSDC),
• the CVRP with heterogeneous fleet (HFCVRP).

Check out the docs to find more variants and options.

Simple example

from networkx import DiGraph
from vrpy import VehicleRoutingProblem

# Define the network
G = DiGraph()
G.add_edge("Source",1,cost=1,time=2)
G.add_edge("Source",2,cost=2,time=1)
G.add_edge(1,"Sink",cost=0,time=2)
G.add_edge(2,"Sink",cost=2,time=3)
G.add_edge(1,2,cost=1,time=1)
G.add_edge(2,1,cost=1,time=1)

# Define the customers demands
G.nodes[1]["demand"] = 5
G.nodes[2]["demand"] = 4

# Define the Vehicle Routing Problem
prob = VehicleRoutingProblem(G, load_capacity=10, duration=5)

# Solve and display solution value
prob.solve()
print(prob.best_value)
3
print(prob.best_routes)
{1: ["Source",2,1,"Sink"]}

Install

pip install vrpy

Requirements

cspy

NetworkX

numpy

PuLP

Documentation

Documentation is found here.

Running the tests

Unit Tests

python3 -m pytest tests/

Benchmarks

To run some non-regression tests on some benchmarks instances (Solomon and Augerat) do

python3 -m pytest benchmarks/

Note that running the benchmarks requires pandas and that it takes a while.

For more information and to run more instances, see the benchmarks.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Bugs

Please report any bugs that you find here. Or, even better, fork the repository on GitHub and create a pull request. Please read the Community Guidelines before contributing. Any contributions are welcome.

vrpy's Issues

JOSS Review: API

Originally from: openjournals/joss-reviews#2408 (comment)

API

• For Functionality documentation: Is the core functionality of the software documented to a satisfactory level (e.g., API method documentation)? above, the API feels a bit light to me. Can you add to it?

• Is vrpy.VehicleRoutingProblem the only "public" interface? I believe so, but if not, please add others to API.html. Btw, maybe add all other classes the prefix "_" to hint the private nature?

Who? All

JOSS Review : general comments

Some of the items may be repeated in other issues. Just wanted to be sure we don't forget anything from openjournals/joss-reviews#2408 (comment).

• Out of the box, running tests in unittests/ folder from PyCharm (on Windows) worked for me. Test_toy took some time to run but maybe that's expected
  => Check and see if one of the tests is too long and change accordingly

• Related to #42, fix the whole benchmarks item

• Out of the box, all tests in benchmarks/ fail. All errors, except the one in test_ortools, are the same:

with open(path + instance_name) as fp:
E FileNotFoundError: [Errno 2] No such file or directory: '../examples/benchmarks/data/P-n16-k8.vrp'
....\examples\benchmarks\cvrp_augerat.py:53: FileNotFoundError

• You seem to have an issue with setting path variables. Please check. test_ortools error is

from ortools.data import (
E ModuleNotFoundError: No module named 'ortools'

• Again, a similar issue. It can't find the ortools folder which is under examples/

• Running mdvrp_cordeau.py fails with

raise KeyError("Node %s missing from initial solution." % v)
KeyError: 'Node 52 missing from initial solution.'

• I suggest renaming the "ortools" folder. The current import statements read as if you have a dependency on the ortools library. It's not obvious that it's just a folder in the upper level.

• Some examples are using numpy.matrix(). It is not recommended to use. Please consider regular numpy ndarrays.
  => This is NetworkX dependent, needs investigation

• Some clean up

• There is a lot of mingling with path variable to append sys.path for folders. I don't think this is necessary and complicates the code/usage --since one now needs to track what's in the path and what's not. I don't see anything special in your library structure that would require altering with path variables. Cannot we resolve these import issues without hacking into the path?

• In test_toy.py, remove "from pytest import raises" --not used. same for test_greedy

• In cvrp_augeratpy, remove "from vrpy.main import VehicleRoutingProblem" --not used

• In benchmarks folder, some files have a main() function, some files don't. Why?

• In examples/ folder, you typically print the best value and best route. Please also ASSERT them. I can run them, but I don't know if the solution is correct or not.

• why is the separation between tests and examples. Why not add these examples to test and assert them.

• is there a way to turn off logging from the underlying solvers like CBC etc? CBC should have some verbosity flag. There are a lot of printouts that are not directly related to this library, and might be confusing for the uninterested user.

• examples.ipync is nice.. but please add ASSERTs along with prints() so that we can verify correctness.

• You might want to add LICENSE information as a header on top of every source code file. Maybe also add License section to README?

• Thinking out loud comment: if you rename main.py to vrp or vehicle_routing, then the imports would read:

from vrpy.vrp import VehicleRoutingProblem
from vrpy.vehicle_routing import VehicleRoutingProblem

which might read a bit more relevant than importing "main"

Other heuristics for initial feasible solution

To have extra columns for the first iteration. After Clarke and Wright, run other (greedy) heuristics such as

• best insertion
• closest node

Clarke and Wright's algorithm generates routes that may violate the num_vehicles constraint, see issue #31.

Is it possible to add a time limit for the cspy subproblem ?

Right now, the paramater time_limit has no effect when solving the subproblem with cspy :

vrpy/vrpy/subproblem_cspy.py

Lines 58 to 68 in aa2623f

	def solve(self, time_limit):
	"""
	Solves the subproblem with cspy.
	Resolves until:
	1. heuristic algorithm gives a new route (column with -ve reduced cost);
	2. exact algorithm gives a new route;
	3. neither heuristic nor exact give a new route.
	Note : time_limit has no effect for the moment
	"""

I am not sure if it is possible to interrupt alg.run() if the time_limit is exceeded

vrpy/vrpy/subproblem_cspy.py

Line 101 in aa2623f

self.alg.run()

This would be handy for testing data sets with a given time limit, but also for a user who wants the best solution found within the time limit. With the lp version, this is done by giving the time limit as an input to the solver.

JOSS Review: Benchmarks

Points related to benchmarks from: openjournals/joss-reviews#2408 (comment)

• Running the benchmarks requires pandas and matplotlib, but pandas and matplotlib are not listed as dependencies (or at least not on the main page)
• Running pytest benchmarks/ failed many of the tests on my Windows computer? The examples worked and the tests passed.

Points related to benchmarks from: openjournals/joss-reviews#2408 (comment)

Structure

In examples/ folder, you typically print the best value and best route. Please also ASSERT them. I can run them, but I don't know if the solution is correct or not.

BTW, why is the separation between tests and examples. Why not add these examples to test and assert them.

Import Errors in tests/benchmarks/

Out of the box, all tests in benchmarks/ fail. All errors, except the one in test_ortools, are the same:

• with open(path + instance_name) as fp:
  E FileNotFoundError: [Errno 2] No such file or directory: '../examples/benchmarks/data/P-n16-k8.vrp'
  ....\examples\benchmarks\cvrp_augerat.py:53: FileNotFoundError
• test_ortools error is

    from ortools.data import (
    E ModuleNotFoundError: No module named 'ortools'

• In test_toy.py, remove "from pytest import raises" --not used. same for test_greedy
• In cvrp_augeratpy, remove "from vrpy.main import VehicleRoutingProblem" --not used
• In benchmarks folder, some files have a main() function, some files don't. Why?

Cordeau

• Running mdvrp_cordeau.py fails with
  raise KeyError("Node %s missing from initial solution." % v)
  KeyError: 'Node 52 missing from initial

Who? @torressa @Halvaros

JOSS Review: Examples

Originally from: openjournals/joss-reviews#2408 (comment)

Structure of examples/

Folder structure

btw, I am not convinced by the structure of the "examples" folder. My expectation as a user would be to see examples of how to solve different variants of VRP problems. The benchmark folder is somewhat okay but the "ortools" folder does not serve that purpose. The user needs to know what ortools is in the first place, and that what is meant by that folder is not really the library but the examples from ortools.

In my mind; examples folder would look like sth like this:

examples/
|_ vrp
|_ vrp_tw
|_ capacited_vrp
|_ capacited_vrp_xxx (xxx is some benchmark name)
|_ multi_depo_cvrp
|_ pickup_delivery

examples.ipync is nice.. but please add ASSERTs along with prints() so that we can verify correctness.

Separation between tests and examples

In examples/ folder, you typically print the best value and best route. Please also ASSERT them. I can run them, but I don't know if the solution is correct or not.

BTW, why is the separation between tests and examples. Why not add these examples to test and assert them.

Problem when running "python3 -m pytest benchmarks/"

The tests failed when I ran the code FOR test_cvrp_augerat.py.... the testing output :

platform win32 -- Python 3.7.6, pytest-5.3.5, py-1.8.1, pluggy-0.13.1

benchmark: 3.2.3 (defaults: timer=time.perf_counter disable_gc=False min_rounds=5 min_time=0.000005 max_time=1.0 calibration_precision=10 warmup=False w
armup_iterations=100000)

plugins: hypothesis-5.5.4, arraydiff-0.3, astropy-header-0.1.2, benchmark-3.2.3, doctestplus-0.5.0, openfiles-0.4.0, remotedata-0.3.2
collected 9 items

benchmarkss\tests\test_cvrp_augerat.py FFFF

Mixed Fleet

I've been playing around with the mixed fleet (HCVRP)

I can't seem to get VRP to run with it returning a TypeError (see attached)

Edge 'cost':
[('Source', 1, [407, 407]), ('Source', 2, [13916, 13916]), ('Source', 3, [189591, 189591]), ('Source', 4, [190473, 190473]), ('Source', 'Sink', 0), (1, 2, [13805, 13805]), (1, 3, [189480, 189480]), (1, 4, [190361, 190361]), (1, 'Sink', [407, 407]), (2, 1, [13694, 13694]), (2, 3, [176398, 176398]), (2, 4, [177280, 177280]), (2, 'Sink', [13925, 13925]), (3, 1, [189098, 189098]), (3, 2, [176331, 176331]), (3, 4, [1943, 1943]), (3, 'Sink', [189328, 189328]), (4, 1, [189515, 189515]), (4, 2, [176749, 176749]), (4, 3, [1943, 1943]), (4, 'Sink', [189746, 189746])]

Demand:
{1: 5, 2: 5, 3: 5, 4: 2}

Also, if it helps, thought i'd share that transforming from a distance/adjacency matrix to a networkx directional graph (DIiGraph) is a little tricky when using a cost for each vehicle.
My limited coding skills were unable to build the graph from the prebuilt networkx functions (namely from_numpy_matrix/array etc) so resorted to list manipulation.

Artifical variables in master problem if initial routes is None

If no feasible initial solution is given, the master problem should still run with artificial variables with a high cost in the cost function.

Format cost correctly if missing edge

Error mentioned here #34 .

If an edge is missing, the initial round trips are created with a high cost :

vrpy/vrpy/clarke_wright.py

Lines 238 to 239 in ed94b88

	if ("Source", v) not in self.G.edges():
	self.G.add_edge("Source", v, cost=1e10)

This cost needs to have the same format as the existing edges, namely it should be a list.

Add benchmarks with other libraries

Following #42, It would be great to add benchmarks with:

• py-ga-vrptw

  • Solomon instances (VRPTW)

• ortools

  • Solomon instances (VRPTW)

  • Augerat instances (CVRP)

Expected format: performance profiles such as

x axis : relative gap with best known solution
y axis : % of data sets solved within gap

How to handle cspy.res_cost object if it has variable length ?

When considering the following constraints :

• maximum number of stops

• load constraints

• duration constraints

resources extension functions are additive, so it is not necessary to define a custom REF.

But when considering time windows, a custom REF is necessary with the cspy.REF_custom method :

How can we handle the fact that the cumulative_res object has a variable length, as it depends on which constraints are activated (load, duration, etc.) ?

For example, we know that the monotone resource is alway first (new_res[0}+=1), but not sure how to handle the other ones.

max duration constraints not met when time windows are active (cspy)

The following (new) test in test_toy.py fails :

def test_all(self):
        prob = VehicleRoutingProblem(
            self.G, num_stops=3, time_windows=True, duration=63, load_capacity=10
        )
        prob.solve(cspy=False)
        lp_best = prob.best_value
        prob.solve(cspy=True)
        cspy_best = prob.best_value
        assert int(lp_best) == int(cspy_best)

The reason is that cspy generates route Source-4-5-Sink which violates the max duration constraint (it has total duration 65). We had not tested duration and time windows constraints simultaneously ^^

There is probably something wrong in the REF, I cannot figure out for the moment. Needs some investigation !

modeling elementarity with resources

Elementarity should be modelled as described below.

So if I understood correctly this requires |V|+1 extra resources (?). One for each vertex, and one for tracking elementarity feasibility. Elementarity is expensive :)

Solomon test fails with n=16 nodes

vrpy/tests/test_cvrptw_solomon_range.py

Line 11 in 134c361

params = list(range(2, 16)) # for some reason n=16 fails

Lp and cspy version yield different results.

JOSS Review: Paper edits

Originally from: openjournals/joss-reviews#2408 (comment) and openjournals/joss-reviews#2408 (comment)

Paper edits

• On page 1 one of the paper, change "thus benefits of" to "thus benefits from"

• I suggest changing the name of the paper to be slightly more specific - "...for solving a range of vehicle routing problems using the column generation approach" - since this seems to be the major contribution?

• For Community guidelines: Are there clear guidelines for third parties wishing to 1) Contribute to the software 2) Report issues or problems with the software 3) Seek support, there doesn't seem to be much in the docs related to this. Can you improve it?

• For State of the field: Do the authors describe how this software compares to other commonly-used packages?, can you add some discussion of other relevant packages? For example, you mention networkx, cspy, Clp, but not other libraries such as ortools or py-ga-VRPTW.

• Is there any reports/performance you can refer to? If full-blown comparison results are not available, even a quick comment might help the user on what to expect from this library? Is this designed to be competitive in terms of runtime and solution quality? OR, there is no such performance claim but instead, it offers an easy-to-use, unified API for many variants of VRP?

• Please mention in the paper that the library does NOT solve the instances to optimality. See my comment on the performance above.

• You have a nice quick start example in the docs. Maybe add that to the paper?

• "The flexibility and genericity of vrpy is strongly due to ... the relevance of cspy.". I am not sure what you mean here, please consider a rephrase

• The high-level intro to the ColGen approach is nice. For the interested reader who might want to see how different variants of VRP can be formulation in this ColGen framework is there a paper or technical report that you can cite/refer? It is not obvious how all of the variants are modeled, the trick happens in the pricing and a reference of details of each formulation would be nice to have.

• Could you please add a word about other libraries and compare/contrast with this one? Does it solve more variants, why should the reader/user consider this library? For example, you mention examples from the ORTools, a comment on the comparison with ORTools and other libraries would be good for the reader to evaluate.

• Any performance to report and/or refer to? There are many standard VRP benchmarks for this purpose, and I see that you already use Solomon etc.

• Add some comments on your strategy for testing the library? In particular; testing invalid conditions and testing behavior (optimal value and route)

Who? @torressa @Kuifje02

Refactoring

Some suggested refactoring from https://github.com/torressa/vrpy/pull/3#issuecomment-662448930

Particularly,

Here are some functions in these files that still need a tune-up:

File	Function	Complexity	Length	Overall	Recommendation
vrpy/main.py	VehicleRoutingProblem._find_columns	52	310.69	1.54	Reduce complexity. Split out functionality
vrpy/main.py	VehicleRoutingProblem._check_arguments	41	218.81	2.63	Reduce complexity. Split out functionality
vrpy/main.py	VehicleRoutingProblem._update_dummy_attributes	22	236.66	3.79	Split out functionality
vrpy/main.py	VehicleRoutingProblem._prune_graph	19	240.82	4.01	Split out functionality
vrpy/main.py	VehicleRoutingProblem._get_num_stops_upper_bound	19	235.85	4.05	Split out functionality

Who? @torressa @Halvaros

Multiple Time Windows

I have a vrp with time windows. However, my routes as long, and so the time windows must be repeated over different days.

For example:

• If a delivery point is served on the first day of a route, it must be served within windows W1 e W2.
• But, if the same delivery point is served on the 2nd day (on a different scenario run), it must respect windows W1+24 and W2+24.
• This should go on for day 3, 4, etc.., repecting the max duration parameter.

Another option would be to provide multiple time windows as input.

Do you have any idea if I can run something like this with VRPY?

Originally posted by @guifcoelho in #40 (comment)

num_vehicles

Hello!

I'm not convinced the num_vehicles parameter is working as expected.
Running a network with 95 nodes and 8 vehicles.
Total demand is 95 (1 per node), load_capacity is 13 (13*8 =104 so some slack)

Solver doesn't appear to restrict to the 8 vehicles and repeats nodes:

I have attached the graph pikle file too, if needed for debug:
EH_graph.txt

Best.
Ed

Gurobi solver option

Also, I haven't personnaly checked that this works as I don't have Gurobi at hand:

vrpy/vrpy/master_solve_pulp.py

Lines 134 to 139 in b4083c2

	elif self.solver == "gurobi":
	gurobi_options = [
	("TimeLimit", self.time_limit),
	("Method", 2), # 2 = barrier
	("Crossover", 0),
	]

It would be great if you could check that the options are currently written, and print the log to make sure it is using barrier wihtout crossover indeed.

The easiest way is to solve the cvrp.py example in folder ortools. Try with and without the options and you will see that with these options much less iterations are necessary!

Originally from this discussio: a4fb99b#r39755684

pickup and delivery option with cspy

Just had a quick google about the pickup and delivery and found this paper.
End of page 10 basically says that the bidirectional algorithm won't work due to dominance conditions for backward labels.
Might still be worth running these with direction="forward" after we figure out how to model it

Originally posted by @torressa in #14 (comment)

Load_capacity constraint breaches

Think the library is a great idea!

Have come across a minor issue with load_capacity breaches.

Unit tests take forever

Unit tests (which are essentially non regression tests) are quite long.

I do think it is a good approach to have them all while developing. But maybe once things are stable we should consider smaller data sets ? Note sure, just thinking and wondering what you think.

NetworkX KeyError on some datasets while calling prob.solve()

The library is great and very easy to use ! While implementing on my own data, I am facing the following error :

Context : This error only occurs when certain delivery locations are added to my input data. What is the root cause of such errors and how can I clean/mitigate the same ? It seems to be a NetworkX specific issue.

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-13-d9e2204baef3> in <module>
      1 from vrpy import VehicleRoutingProblem
      2 prob = VehicleRoutingProblem(G, load_capacity=4)
----> 3 prob.solve()

~\anaconda3\lib\site-packages\vrpy\main.py in solve(self, initial_routes, preassignments, pricing_strategy, cspy, exact, time_limit, solver, dive, greedy)
    176 
    177         # Initialization
--> 178         self._initialize()
    179 
    180         # Column generation

~\anaconda3\lib\site-packages\vrpy\main.py in _initialize(self)
    263         else:
    264             # Initial solution is computed with Clarke & Wright (or round trips)
--> 265             self._get_initial_solution()
    266         # Initial routes are converted to digraphs
    267         self._convert_initial_routes_to_digraphs()

~\anaconda3\lib\site-packages\vrpy\main.py in _get_initial_solution(self)
    469                 self.G, self.load_capacity, self.duration, self.num_stops
    470             )
--> 471             alg.run()
    472             logger.info("Initial solution found with value %s" % alg.best_value)
    473             self._initial_routes = alg.best_routes

~\anaconda3\lib\site-packages\vrpy\clarke_wright.py in run(self)
     31     def run(self):
     32         """Runs Clark & Wrights savings algorithm."""
---> 33         self._initialize_routes()
     34         self._get_savings()
     35         for (i, j) in self._ordered_edges:

~\anaconda3\lib\site-packages\vrpy\clarke_wright.py in _initialize_routes(self)
     43                 # Create round trip
     44                 round_trip_cost = (
---> 45                     self.G.edges["Source", v]["cost"] + self.G.edges[v, "Sink"]["cost"]
     46                 )
     47                 route = DiGraph(cost=round_trip_cost)

~\anaconda3\lib\site-packages\networkx\classes\reportviews.py in __getitem__(self, e)
    928     def __getitem__(self, e):
    929         u, v = e
--> 930         return self._adjdict[u][v]
    931 
    932     # EdgeDataView methods

KeyError: 29

Any help would be much appreciated !!

General Question : Is it possible to have some of the routes span multiple days in periodic VRP ?

Thanks again for developing this library and the prompt responses to all of the issues. It is a great alternative to ORTools for VRP problems and much easier to use !!

Is it possible to have some of the routes span multiple days in periodic VRP ? e.g. I am planning routes over a month and some customers are very far away, requiring a round trip spanning multiple days. Something like below -

Day 1, Route 1 -> Source -> Customer 1
Day 2, Route 1 -> Customer 1 -> Sink ( Back to Depot ) -> Customer 2 -> Sink

Any direction or links where you have seen this implemented would also be great. I understand that multiple trips may or may not fit into the existing code-base easily.

Implement Clark & Wright 's savings algorithm as initial solution

Having a good initial feasible solution is always a good start. Clark & Wright's saving algorithm is a good option (good empirical results and easy to implement).

It can be adapted for time windows as well.

Diving heuristic checking and testing

I've implemented the diving heuristic (I think).

vrpy/vrpy/master_solve_pulp.py

Lines 37 to 78 in aaf2b51

	def solve_and_dive(self, max_depth=3, max_discrepancy=3):
	"""
	Implements diving algorithm with Limited Discrepancy Search.
	From : `Sadykov et al. (2019)`_.
	.. _Sadykov et al. (2019): https://pubsonline.informs.org/doi/abs/10.1287/ijoc.2018.0822
	"""
	self._formulate()
	self._solve()
	if self.prob.status != 1:
	return
	depth = 0
	tabu_list = []
	while depth <= max_depth and len(tabu_list) <= max_discrepancy:
	a_relax_vars = list(var for var in self.prob.variables()
	if abs(var.varValue - round(var.varValue)) != 0)
	vars_to_fix = [
	var for var in a_relax_vars if var.name not in tabu_list
	]
	if vars_to_fix:
	var_to_fix = min(
	vars_to_fix,
	key=lambda x: abs(x.varValue - round(x.varValue)))
	value_to_fix = 1
	self.prob += var_to_fix <= value_to_fix
	self.prob += var_to_fix >= value_to_fix
	self._solve()
	# if NOT optimal.
	# status code from : https://github.com/coin-or/pulp/blob/master/pulp/constants.py#L45-L57
	if self.prob.status != 1:
	logger.debug(" Ran diving with LDS and fixed %s vars",
	len(tabu_list))
	break
	tabu_list.append(var_to_fix.name)
	depth += 1
	else:
	logger.debug(" Ran diving with LDS and fixed %s vars",
	len(tabu_list))
	break
	self._solve()
	return self._get_total_cost_and_routes()

Seems to mostly work for the benchmarks instances: fails for some cases, but is really fast. However, I'm not entirely sure whether it should be run just at the last iteration as it now (when the optimal solution to the LP relaxation has been found)

vrpy/vrpy/main.py

Lines 189 to 191 in aaf2b51

	if self._dive:
	self._best_value, self._best_routes_as_graphs = self._solve_and_dive(
	)

OR all the way through the column generation procedure (?). The paper just makes me more confused every time I read it 😆

Anyway, if I've implemented correctly, might be worth comparing between the solution given by the integer master, both in objective value and solution time.

Error while using solver="gurobi" option on Windows 10

When calling prob.solve with a "gurobi" solver, I am getting an error in between the execution. Can you help in understanding why this may be happening ?

The error doesn't appear when I am solving a simple VRP for a single day.

Setting parameters and preparing NetworkX graph for solving periodic VRP problem

Solving PVRP
INFO:vrpy.main:new upper bound : max num stops = 4
INFO:vrpy.main:iteration 0, 4050000563644.0
INFO:vrpy.main:iteration 1, 4040000563816.0
INFO:vrpy.main:iteration 2, 4040000563816.0
INFO:vrpy.master_solve_pulp:total cost = 4040000563816.0
---------------------------------------------------------------------------
PulpSolverError                           Traceback (most recent call last)
<timed exec> in <module>
---------------------------------------------------------------------------
PulpSolverError                           Traceback (most recent call last)
<timed exec> in <module>

<ipython-input-6-c5fb3f310298> in run_PVRP(DISTANCES, df_nodes, demands, service_levels, city_name, time_limit, truck_capacity)
     44 
     45     print("\nSolving PVRP")
---> 46     prob.solve(solver="gurobi")
     47 
     48     print("\n Algorithm Run Completed")

~\code\vrpy\main.py in solve(self, initial_routes, preassignments, pricing_strategy, cspy, exact, time_limit, solver, dive, greedy)
    227                 self._solver,
    228             )
--> 229             schedule.solve(self._time_limit)
    230             self._schedule = schedule.routes_per_day
    231 

~\code\vrpy\schedule.py in solve(self, time_limit)
     43 
     44         self._formulate()
---> 45         self._solve(time_limit)
     46         # self.prob.writeLP("schedule.lp")
     47         logger.debug("Status: %s" % pulp.LpStatus[self.prob.status])

~\code\vrpy\schedule.py in _solve(self, time_limit)
     94         elif self.solver == "gurobi":
     95             gurobi_options = [("TimeLimit", time_limit)]
---> 96             self.prob.solve(pulp.GUROBI_CMD(options=gurobi_options))
     97 
     98     @property

~\anaconda3\lib\site-packages\pulp\pulp.py in solve(self, solver, **kwargs)
   1881         #time it
   1882         self.solutionTime = -clock()
-> 1883         status = solver.actualSolve(self, **kwargs)
   1884         self.solutionTime += clock()
   1885         self.restoreObjective(wasNone, dummyVar)

~\anaconda3\lib\site-packages\pulp\apis\gurobi_api.py in actualSolve(self, lp)
    282 
    283         if return_code != 0:
--> 284             raise PulpSolverError("PuLP: Error while trying to execute "+self.path)
    285         if not os.path.exists(tmpSol):

Hyper-heuristic for subproblem algorithm selection

One for future @Halvaros:

There are three different ways of solving the subproblems (LP, Greedy and cspy) and it is not clear beforehand which is one is going to be better/faster. I think it'd be a cool idea to implement a hyper-heuristic to apply different ones adaptively (based on some criteria like solution quality and/or speed).
I'm not too sure about which one would be the best one, but I have few papers that are good starting points:

• Pretty recent review by Drake et al. (2019). We are interested in selection hyper-heuristics.
• I've used the one by Özcan et al. (2010) also in a column generation scenario (code to be public soon) but it's pretty old and a overly simplistic (cool name though).

I propose the following steps

• Comparison of different subproblem performance per benchmark (to justify the hyper-heuristic implementation in the first place)
• Research of hyper-heuristics (shop around for good algorithms, nothing too computationally expensive)
• Implementation (pick one, implement it, and see how it performs)

self.masterproblem: _MasterSolvePulp = None SyntaxError: invalid syntax

Hello,
i try
python -m pytest tests/

error

../../../../Library/Python/2.7/lib/python/site-packages/_pytest/assertion/rewrite.py:304: in load_module
    exec(co, mod.__dict__)
tests/test_toy.py:5: in <module>
    from vrpy import VehicleRoutingProblem
vrpy/__init__.py:2: in <module>
    from vrpy.vrp import VehicleRoutingProblem
     File "vrpy/vrp.py", line 108
       self.masterproblem: _MasterSolvePulp = None
                         ^
SyntaxError: invalid syntax

Custom REF for Time Windows

The correct time-window resource propagation doesn't work.

Forward time resource:

I think it might be related to the backward extension, so requires resurrecting of the backward custom REF.
Code here

Complete documentation

I started working on the docs, trying to keep the same spirit and structure as cspy. Feel free to modify anything you want, in any way you want, or to simply make suggestions.

• Complete the examples
• Detail the VehicleRoutingProblem class
• Rename vrpy.main (?)

Distribution & collection option with cspy

The following variant described in Salani and Righini's article should be fairly easy to implement, now that we are confident with time windows and its cutom REF :

For the backwards custom REF :

JOSS Review: Docs

Comments about Docs

• Math Background sections have a lot of relevant references, but most are not cited in the text.

• The section "Why use the cspy library?" is somewhat misleading in the doc section of the "VRPy" library. We are not directly using the cspy here. Maybe call if "Solving the Pricing using cspy" or sth similar?

• In Index.html it reads "solving Vehicle Routing Problems (VRP)". What you probably mean is solving "instances" of different types of Vehicle Routing Problems. Here you should definitely mention that the library is NOT guaranteed to find optimal solutions, and maybe a word on the solution quality of what it typically achieves.

• Add performance profiles to docs.

Citing the library

Hi
Hopefully a quick one, looking to cite the library in my masters thesis, is their a particular paper/citation you have preference for?
Thanks for your hard work!
Best.
Ed

P-n23-k8.vrp data set does not run (cspy)

For some reason the data set P-n23-k8.vrp from Augerat does not run with cspy, I cannot figure out why for the moment (all other data sets are ok, for some reason this one does not). It is in the data folder.

P-n23-k8 cspy
=========
vrpy.main - INFO - new upper bound : max num stops = 8
vrpy.main - INFO - iteration 0, 1098.4
Traceback (most recent call last):
  File "cvrp_augerat.py", line 219, in <module>
    data.solve(cspy=cspy, exact=True, time_limit=60)
  File "cvrp_augerat.py", line 145, in solve
    prob.solve(cspy=cspy, exact=exact, time_limit=time_limit)
  File "../..\vrpy\main.py", line 149, in solve
    self.routes, more_routes = subproblem.solve(time_limit)
  File "../..\vrpy\subproblem_cspy.py", line 103, in solve
    logger.debug("cost = %s" % self.alg.total_cost)
  File "../../../cspy\cspy\algorithms\bidirectional.py", line 176, in total_cost
    raise Exception("Please call the .run() method first")
Exception: Please call the .run() method first

How to make sure time limit is not exceeded

If the colgen procedure searches for variables until the time limit is passed, there is no time left for the final MIP.

f0d5b7b#r39585343

Different possibilities:

• take a few seconds from the input time limit to solve the last MIP
• warn the user that the total time may exceed the input time limit
• ...

Question : Is there a simple starter example of Periodic VRP with a month of planning period ?

In the documentation, I noticed that just setting the frequency of visits for each node is given as an option. How do I set the duration ( planning period ) and define periodicity in a better way ?

Also - how would I get the routes for each day in the planning period from the solved problem.

I have a central depot where nodes ( customers ) are to be visited a certain number of times every month.

G.nodes[1]["frequency"] = 2
prob.periodic = True

Apologies if the question is very basic. I am new to vehicle routing problems. Any help would be appreciated !

Dead code ?

Did you write this bit of code for a particular reason ? I may be wrong but I don't think it is ever read (tests pass when it is commented).

vrpy/vrpy/subproblem_lp.py

Lines 14 to 18 in 662ad39

	def __init(self):
	# Attribute for the pulp.LpProblem
	self.prob = None
	# Attribute for the flow varibles
	self.x = None

warm start

Hi,
does VRPy support warm start strategy?
I mean add feasible solution(partly or completely assignment) in master or sub-problem which is solved by branch and cut framework.

Ideas to boost the code

Not really an issue, just a place to keep track of our ideas to speed up execution of the code.

• Better initial solution (e.g., Clarke & Wright)
  • If no time windows/pickup delivery/distribution collection
  • otherwise
• Preprocessing
  • Remove infeasible edges
  • Strengthen time windows
  • Remove some "bad" edges at each iteration for each subproblem (those with a high reduced cost, details here, section 2.1)
  • Upper bound on number of steps (details here, section 2.3)
  • p-nearest neighbour (mentioned here)
• Cuts
  • Symmetry breaking
    • if the graph is undirected, and that no time windows are enforced, require that the index of the first node of the path < index of last node (divides the number of possible paths by 2)
  • 2-path cuts at root node -> not sure about this one
• cspy heuristics (need work to speed up see torressa/cspy#40)
  • GreedyElim
  • Tabu
• Add more than one column at each iteration
• Code profiling to locate bottlenecks

Error : Float Object not subscriptable

I am getting this error intermittently while solving for a PVRP with a planning period of 24 days and a constraint on duration. It happens for subsets of my data and I was hoping for some direction to understand why this is happening. The error does not happen when I just use the Cost Matrix.

 45     prob.solve(time_limit = time_limit)

~\Desktop\Supply_Chain_Tool_Streamlined\code_w_balanced_schedules\vrpy\main.py in solve(self, initial_routes, preassignments, pricing_strategy, cspy, exact, time_limit, solver, dive, greedy)
    178 
    179         # Initialization
--> 180         self._initialize()
    181 
    182         # Column generation

~\Desktop\Supply_Chain_Tool_Streamlined\code_w_balanced_schedules\vrpy\main.py in _initialize(self)
    279             self._get_initial_solution()
    280         # Initial routes are converted to digraphs
--> 281         self._convert_initial_routes_to_digraphs()
    282         # Initialize parameters for stopping criteria
    283         self._more_routes = True

~\Desktop\Supply_Chain_Tool_Streamlined\code_w_balanced_schedules\vrpy\main.py in _convert_initial_routes_to_digraphs(self)
    514             edges = list(zip(r[:-1], r[1:]))
    515             for (i, j) in edges:
--> 516                 edge_cost = self.G.edges[i, j]["cost"][0]
    517                 G.add_edge(i, j, cost=edge_cost)
    518                 total_cost += edge_cost

TypeError: 'float' object is not subscriptable

For reference, the code used for setting up the problem is below : [ I am using a DISTANCE matrix similar to the OR tools example, and incorporating time by assuming an AVERAGE_SPEED in km/hour. Duration constraint is set as 10 hours per day of the planning period ]

A = matrix(DISTANCES, dtype=[("cost", int)])
G_d = from_numpy_matrix(A, create_using=nx.DiGraph())
 
# Transform time matrix into DiGraph
# Average speed of vehicle is assumed to be 50 km/hr
# Time unit is in minutes, distance unit is in km    
TRAVEL_TIMES = [[round(60*float(j)/AVERAGE_SPEED,0) for j in i] for i in DISTANCES]

A = matrix(TRAVEL_TIMES, dtype=[("time", int)])
G_t = from_numpy_matrix(A, create_using=DiGraph())

# Merge
G = nx.compose(G_d, G_t)

###Adding frequencies and making the problem periodic in nature
##Setting the frequency for each node
set_node_attributes(G, values=service_levels, name="frequency")

# The demands are stored as node attributes
set_node_attributes(G, values=demands, name="demand")

# The depot is relabeled as Source and Sink
G = relabel_nodes(G, {0: "Source", len(DISTANCES)-1: "Sink"})

#Load capacity is set to the load capacity of each truck. Assuming a 10 hour working day to set duration of routes
#10 hours is 600 minutes
prob = VehicleRoutingProblem(G, load_capacity=truck_capacity, duration = 600)

# Setting the planning horizon to 24 days - 6 days working in each week
prob.periodic = 24

exact = False, which metaheuristic?

Hello again!

Is it possible to know which metaheuristic is called from cspy when exact = False?

I can see there is a _solver in the vars of the VehicleRoutingProblem but unsure what this relates to

Best
Ed

When locking routes, if all vertices are locked, skip column generation

If a user locks routes, and that all vertices of the graph are assigned to a route, column generation should be skipped since the solution is complete and should not be improved.

Implement Branching with Route Enumeration

For a different column generation-based heuristic, Branching with Route Enumeration works better (than diving) for the VRP.
The algorithm is described here

Testing: Benchmark Instances

That's cool ! I also tested the Solomon case with the 50 first vertices and with the LP version of the sub problem and was able to find the solution of the benchmarks. This is reassuring !The solution is plotted below :

For the speed we will probably have to do some profiling to identify the bottlenecks, and maybe some acceleration tricks should be implemented, like the one you mentioned. We will see. Another interesting figure is the rate of convergence of the procedure :

Most of the time is spent trying to prove optimality. And actually it fails, as I set a 1000 iteration limit.

But in all cases this is promising and interesting ! Eager to do some comparisons with or-tools !

Originally posted by @Kuifje02 in torressa/cspy#33 (comment)

Raise ValueError if demand at Source or Sink is > 0

This being said, you have still pointed out something interesting, it might be a good idea to raise an error if the Sink's demand is not 0.
And If you need really a demand at the sink, you can split the Sink into two vertices dummy_node, and Sink with a cost=0 between the two, and the demand at the dummy_node.

Originally posted by @Kuifje02 in #22 (comment)

sphinx formats docstring Attr on same line

Sphinx formats docstring Attributes on same line :

I noticed that if I skip a line between attributes, its fine, but I assume this is not normal.

The issue was reported here but the solution (add blank line between description and Args does not work)

Formulate master pulp by columns

As mentioned here, for the diving heuristic to work, for some speed up, it would be good to rework master_solve_pulp.py such that it doesn't have to be reformulated in every iteration of the column generation procedure.

For a column generation friendly way of updating the constraints, one can formulate the problem by columns (seen an example).

The idea is to

1. create empty constraints using pulp.LpConstraintVar, with only the sign (<=, >=) and RHS specified.
2. Then place variables pulp.LpVariable in already existing constraints with the appropriate coefficient, using the e parameter. Here, one can use pulp operations like pulp.lpSum to add variables to multiple constraints at once (this can be seen in the example)

To update the constraints throughout the column generation procedure, the constraints has have to preserved. For example as a dictionary in an attribute.

Constraints Converted

• Set Covering
• Vehicle bound

Variables Converted

• route selecting (y)
  • Simplest case
  • With vehicle bound
• Drop
• Artificial

Type Error while calling prob.solve() - __init()__ got an unexpected keyword argument 'REF_forward'

I am facing issues in using the library. While running the example in the documentation - I keep getting a type error
init() got an unexpected keyword argument 'REF_forward'

When I set the pricing_strategy variable as "PrunePath", I don't get this error. However, it seems like the solver is only giving me the MIP solution in that case.

Environment : Anaconda 3 ( Python 3.7.6 ) on Windows 10.

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-23-7ab8d68a34cd> in <module>
 #prob.solve()

~\anaconda3\lib\site-packages\vrpy\main.py in solve(self, initial_routes, preassignments, pricing_strategy, cspy, exact, time_limit, solver)
    159                 cspy,
    160                 exact,
--> 161                 solver,
    162             )
    163 

~\anaconda3\lib\site-packages\vrpy\main.py in _find_columns(self, k, more_routes, no_improvement, time_limit, pricing_strategy, cspy, exact, solver)
    272         if not more_routes or pricing_strategy == "Exact":
    273             subproblem = self._def_subproblem(duals, cspy, exact, solver,)
--> 274             self.routes, more_routes = subproblem.solve(time_limit)
    275 
    276         # Keep track of convergence rate

~\anaconda3\lib\site-packages\vrpy\subproblem_cspy.py in solve(self, time_limit)
     90                     REF_forward=self.get_REF("forward"),
     91                     REF_backward=self.get_REF("backward"),
---> 92                     REF_join=self.get_REF("join"),
     93                 )
     94             else:

TypeError: __init__() got an unexpected keyword argument 'REF_forward'