The Multi-depot Periodic Vehicle Routing Problem Abstraction, Reformulation and Approximation

The Multi-Depot Periodic Vehicle Routing Problem (MDPVRP) is the problem of designing, for an homogeneous fleet of vehicles of capacity Q, a set of routes for each day of a given p-day period. The routes of day k must be executed by m k vehicles based at the depot assigned to day k. Each vehicle performs only one route per day and each vehicle route must start and finish at the same depot. Each customer i may require to be visited on f i (say) di.erent days during the period and these visits may only occur in one of a given number of allowable daycombinations. For example, a customer may require to be visited twice during a 5-day period imposing that these visits should take place on Monday-Thursday or Monday-Friday or Tuesday-Friday. The MDPVRP consists of simultaneously assigning a day-combination to each customer and designing the vehicle routes for each day of the planning period so that each customer is visited the required number of times, the number of routes on each day does not exceed the number of vehicles available at the depot assigned to that day and the total cost of the routes is minimized.