weird behaviour with mixed fleet

[willemvandecorput]

I am using VRPy to solve the vehicle routing problem. I have done some tests with it using costs i obtained through PgRouting using an OSM road network. These tests had a depot (source/sink) location and about 25 delivery locations. These tests worked great. Now what I want to do is use two types of vehicles (electric vs diesel). In the VRP problem, these vehicles have different costs per segment of my network. For segments inside a zero emission zone, the costs for the diesel cars are multiplied by 1000 in order to make sure the VRP solver never sends diesel cars into the zero emission zone. The costs for routes outside the zone are the same for both types of trucks.

After adding the costs for both types of vehicles, specifying additional parameters like number of stops, number of vehicles etcetera, the solver kept running infinitely and when i used the time_limit parameter, it returned: Problem Infeasible. The thing is, I have checked manually that it is feasible, in fact, there are many solutions that avoid the 1000 cost edges completely. I have also run some tests on a more basic test case which features 6 delivery locations and edges between them all in both directions. When i use a num_stop of 2 and num_vehicles like [2, 1] it works. But when i use a num_stop of 6 and a num_vehicles like [1, 0], which should of course also be possible, it doesn't work.

Here is the example i created:

from networkx import DiGraph
from vrpy import VehicleRoutingProblem

G = DiGraph()

for v in range(1, 7):
       if v < 3:
        G.add_edge("Source", v, cost=[10, 1000])
        G.add_edge(v, "Sink", cost=[10, 1000])
       else:   
        G.add_edge("Source", v, cost=[10, 10])
        G.add_edge(v, "Sink", cost=[10, 10])

for v in range(1, 7):    
   for a in range(1, 7):
      if a == v:
         continue
      if v < 3:
        if a < 3:
           G.add_edge(v, a, cost=[10, 1000])

        else: 
            G.add_edge(v, a, cost=[10, 1000])
       
      else:
         if a < 3:
           G.add_edge(v, a, cost=[10, 1000])

         else: 
            G.add_edge(v, a, cost=[10, 10])

vrp = VehicleRoutingProblem(G, 
                            mixed_fleet = True,
                            num_stops = 6,
                            fixed_cost = [0, 0],
                            load_capacity = [1, 1],
                            num_vehicles=[1, 0])

vrp.solve()

print(vrp.best_routes)

[willemvandecorput]

EDIT: when i set cspy=False it works for the example above, but still behaves the same for my actual case

[willemvandecorput]

I've narrowed the issue a bit further, I noticed that as long as all the deliveries can be done with the type 1 vehicle, the solver works, but as soon as even 1 location needs to be done with the type 2 vehicle, it does not work

[Kuifje02]

Its possible that the problem becomes computionally more difficult. Can you check the logs of the solver ? Are you sure the status is infeasible and not "no solution found" ?

[willemvandecorput]

Yes i'm sure it says problem infeasible. It could be that it becomes too computationally difficult. However, even if is test with 12 points, num_stop=4 and num_vehicles=[2, 1] (which should be possible), it also says infeasible. Like i said it seems to me like the solver does not recognize that it should use vehicle type 1 for certain routes and vehicle type 2 for other ones

raise Exception("problem " + str(pulp.LpStatus[self.prob.status]))
Exception: problem Infeasible

[torressa]

In this case, this can be fixed by adding slightly better initial routes as those from _RoundTrip are infeasible:

--- a/vrpy/vrp.py
+++ b/vrpy/vrp.py
@@ -921,7 +921,14 @@ class VehicleRoutingProblem:
                 % (alg.best_value, len(alg.best_routes))
             )
             self._initial_routes += alg.best_routes
-
+        elif self.mixed_fleet:
+            alg = _Greedy(self.G, self.load_capacity, self.num_stops, self.duration)
+            alg.run()
+            logger.info(
+                "Greedy solution found with value %s and %s vehicles"
+                % (alg.best_value, len(alg.best_routes))
+            )
+            self._initial_routes += alg.best_routes

I am not sure this would be the case in general though.

[willemvandecorput]

Hi @torressa ,

Thanks for your suggestion! I tried passing the routes of a solution I found as initial routes, however, it doesn't seem to influence the solver: it just runs infinitely like before and with the time limit it returns Problem Infeasible. Even though I passed the routes of a feasible solution to the solver. Should i maybe specify somehow which of the initial routes correspond to which vehicle type? Any further information on mixed fleet problems and initial routes would be very welcome as well.

[ljwolf]

I also have issues with the multi-vehicle cases using the development version on GitHub.

I installed the package from GitHub because the new gurobipy does not support passing options as a list of tuples, but requires you to do the standard dictionary unpacking (So, pulp.GUROBI(msg=False, options=[("Method", 2)]) becomes pulp.GUROBI(msg=False, Method=2).

Using vrpy installed from GitHub, the problem becomes infeasible when there isn't enough of the first truck type to solve the problem alone. Indeed, I noticed by inspecting the underlying master problem, only the first truck count constraint was being augmented; the second was never modified.

Strangely enough, this behavior is not happening for me on release version 0.5.1 from pypi.