MDVRP

The Multi-Depot Vehicle Routing Problem (MDVRP) is a variant of the CVRP in which vehicles are based in different depots.

Instance formats

The demo reads instances in the standard “Cordeaux” format. See this repository for details.

The first line contains the following information:

type m n t

type: it’s equal to 2 for the MDVRP
m: number of vehicles
n: number of customers
t: number of depots

The next t lines contain, for each depot , the following information:

D Q:

D: maximum duration of a route (not supported in this demo)
Q: maximum load of a vehicle

The next lines contain, for each customer, the following information:

i x y d q f a list e l

i: customer id
x: x coordinate
y: y coordinate
d: service duration (not supported in this demo)
q: demand
f: frequency of visit (not used in MDVRP)
a: number of possible visit combinations (not used in MDVRP)
list: list of all possible visit combinations (not used in MDVRP)
e: beginning of time window (not supported in this demo)
l: end of time window (not supported in this demo)

Run instances

There are two ways to run a specific instance:

Command line

You can solve an instance by specifying different parameters directly in the command line, like this:

python MDVRP.py -i <instance path> -t <time limit> -s <solver_name>

CPLEX solver can be used only with the academic version. When using CPLEX solver on a Windows computer, one should give its path: -p <path to CPLEX>.

Demo code

Get data

data = read_instance(instance_name,folder_data)

An example of the contents of data :

nb_depots = 2
nb_customers = 3
vehicle_capacity = 60
cust_demands = [15,52,65]
cust_coordinates = [[55.21,44.36],[57.81,53.27]]
depot_coordinates = [[54.69,57.36],[54.31,65.23]]

Add vehicle types

Here we define a separate vehicle type for each depot. Each vehicle type is characterized by a depot where vehicles of this type start and end.

# add vehicle types
for i in range(data.nb_depots):
    model.add_vehicle_type(id=i + 1,
                           start_point_id=i,
                           end_point_id=i,
                           capacity=data.vehicle_capacity,
                           max_number=data.nb_customers,
                           var_cost_dist=1)

Here the start point id and the end point id corresponds to the id of depot assigned. Moreover, the maximum number of vehicle cannot be less than number of customers.

Add depots and customers

# add depots
for i in range(data.nb_depots):
    model.add_depot(id=i)

# add all customers
for i in range(data.nb_customers):
    model.add_customer(id=i + data.nb_depots + 1,
                       demand=data.cust_demands[i])

Note

IDs of depots and customers should be different.

Add links

# Compute the links between depots and other points
for depot_id in range(data.nb_depots):
    for i, cust_i in enumerate(data.cust_coordinates):
        dist = compute_euclidean_distance(
            cust_i[0],
            cust_i[1],
            data.depot_coordinates[depot_id][0],
            data.depot_coordinates[depot_id][1])

        model.add_link(start_point_id=depot_id,
                       end_point_id=i + data.nb_depots + 1,
                       distance=dist
                       )

# Compute the links between points
for i,cust_i in enumerate(data.cust_coordinates):
    for j in range(i + 1, len(data.cust_coordinates)):
        dist = compute_euclidean_distance(cust_i[0],
                                          cust_i[1],
                                          data.cust_coordinates[j][0],
                                          data.cust_coordinates[j][1])

        model.add_link(start_point_id=i + data.nb_depots + 1,
                       end_point_id=j + data.nb_depots + 1,
                       distance=dist
                       )

}

Set parameters

model.set_parameters(time_limit=30, solver_name="CLP")

Solve model

model.solve()

Print solution

You can output the solution using the print() function

if (model.solution.is_defined())
    print(model.solution)

or you can analyze the solution manually by retrieving each route. For and example, consult the last section of the demo CVRP.