VRP Variants

Multi-Depot VRP (MDVRP)

A company may operate several depots from which it serves its customers. If the customers are clustered around the depots, the distribution problem can be modeled as a set of independent VRPs. However, when customers and depots are intermingled, a Multi-Depot Vehicle Routing Problem (MDVRP) must be solved instead.

An MDVRP requires the assignment of customers to depots. A fleet of vehicles is based at each depot; each vehicle originates from one depot, services the customers assigned to that depot, and returns to the same depot. The objective is to service all customers while minimizing the number of vehicles and the total travel distance.

Formal description

Objective: minimize the vehicle fleet and the sum of travel time, where the total demand of the commodities is served from several depots.
Feasibility: a solution is feasible if each route satisfies the standard VRP constraints and begins and ends at the same depot.
Formulation: the VRP is extended to the case of multiple depots, so the vertex set is written as $V = {v1, …, vn} ∪ VD$ , where $VD = {depot vertices}$ are the vertices representing the depots. A route i is then defined by $R_i = (d, v1, …, d)$ , with $d ∈ VD$ — that is, each route starts and ends at the same depot. The cost of a route is computed exactly as in the standard VRP.