CODEWITHSUNDEEP
or-tools
tcokyasar
tcokyasar

Reputation: 592

Modeling Multiple Depot Vehicle Scheduling Problem in OR-Tools

Is it possible to solve the Multiple Depot Vehicle Scheduling Problem (MDVSP) in OR-tools?

The problem is detailed in this paper, but here is a brief summary.

We are given a set of depots and the number of available vehicles at each. We are given a set of timetabled trips, and we know the origin, destination, start time, end time, and a set of depots that can serve a given trip. While connecting two trips, that is assigning a vehicle to serve for two trips sequentially, there may be an unoccupied travel, so called a dead-head trip. There are also dead-heads while going from a depot to the first trip and returning from the last trip to a depot. The objective is to minimize the sum of all dead-head trip costs while ensuring each trip is served by exactly one vehicle and the number of vehicles used does not exceed the availability. (Other trips/links, i.e., occupied trips, must in any case need to be served/traversed; so, there is no need to include them in the objective).

Upvotes: 0

Views: 1284

Answers (1)

Mizux
Mizux

Reputation: 9291

Seems you want to take into account the arc cost only if vehicle is empty. (note: fixed typo)

AFAIK, there is no easy way to do it using OR-Tools. In C++ you may use the DimensionDependentDimension and returning the arc cost if a capacity dimension is zero, and zero otherwise...

  1. Also I'm curious why you would like to only count dead-trip e.g. if the overall vehicle route is several time longer with very few dead-trip instead of a shorter route with few dead-trip why would you want to incentive the first one ? e.g. a route of 100km with 1km dead-trip is two time better than a 50km route with 2km dead-trip...

  2. For multiple depots please take a look at vrp_starts_ends.py

  3. For TimeWindows: vrp_time_windows.py

  4. Did you take a look at the documentation ? e.g. https://developers.google.com/optimization/routing/cvrp

  5. using routing.NextVar(A).SetValues([A, B]) you can force the chain A->B
    ref: https://github.com/google/or-tools/blob/49b6301e1e1e231d654d79b6032e79809868a70e/ortools/constraint_solver/routing.h#L1364-L1366
    note: Solver won't have the possibility to use A->C->B even if is shorter than A->B->C or C->A->B (supposing TW allow both of them...)

Upvotes: 1

Related Questions