Schedule of several depots

Question

I play with algorithms and ILP for the single depot dispatching task (SDVSP), and now I want to expand my knowledge on the problem of planning multiple vehicles (MDVSP), since I would like to use this knowledge in my project.

Regarding the question, I found and implemented several algorithms for MDSVP. However, I am very curious to know how to determine the number of required warehouses (and placements). Unfortunately, I could not find any resources that do not suggest / require that the repositories be installed. So my question will be: how can I get closer to MDVSP, in which I can determine the number and location of warehouses?

(Change) To clarify: Suppose we are given a set of trips T ₁ , T ₂ ... T _n , as usual in SDVSP or MDVSP. After several trips, you can return to the depot. Departure and return to warehouses usually occurs only at the beginning and at the end of the day. But as a complement to normal problems, we can now determine the number and location of our warehouses, against setting up a depot.

The goal is to find a solution in which all trips are managed with minimal cost. The cost consists of the amount of the dead point (the distance that the car must travel between trips, as well as from and to the warehouses), a fixed cost K for the car and a fixed cost C at the depot.

Hope this mitigates the issue somewhat.

Answer 1

The standard approach includes adding | V | binary variables in ILP, one for each node, where x_i = 1 if v_i is a depot and 0 otherwise.

However, as the question is currently formulated, all x_i values ​​will be equal to zero, since there is no “advantage” of creating a node department and total cost = (other cost factors) + sum_i (x_i) * FIXED_COST_PER_DEPOT.

Perhaps the question should be updated with some other restriction regarding the range of the car. For example, a car can travel so many miles before returning to the depot.