697. A multi-phase methodology for solving distribution problems with limited supply at the depots
Invited abstract in session ME-19: Vehicle Routing, cluster Combinatorial Optimization.
Monday, 16:15-17:45Room: FENH105
Authors (first author is the speaker)
| 1. | Pedro Piñeyro
|
| Deparment of Operations Research, Computer Science Institute (InCo), Facultad de Ingeniería, Universidad de la República | |
| 2. | Javier de Prado
|
| Facultad de Ingeniería, Universidad de la República | |
| 3. | Sandro Moscatelli
|
| Facultad de Ingeniería, Universidad de la República | |
| 4. | Libertad Tansini
|
| Facultad de Ingniería, Universidad de la República | |
| 5. | Omar Viera
|
| Operations Research; Computer Science Institute, Facultad de Ingeniería, Universidad de la República |
Abstract
We address an extension of the multi-depot vehicle routing problem (MDVRP), where the supply capacity of the depots is limited. The objective is to determine a set of routes starting and ending at each depot, minimizing the total distance travelled and subject to the supply capacity of each depot and the capacities of the vehicles. We refer to this problem as the Capacitated Multi-Depot Vehicle Routing Problem (CMDVRP). Distribution problems, like the CMDVRP, can be found in recent real-life applications, such as emergency facilities location-routing and city logistics problems. The CMDVRP is an NP-hard problem, since it can be considered an extension of the (MDVRP), in turn an extension of the classical Vehicle Routing Problem (VRP). To solve the CMDVRP, we propose a multi-phase methodology based on the “cluster first, route second" approach. The initial phase consists of the assignment of customers to depots, and the final phase produces the routing of the VRPs related to all depots. Between these two phases, there is an intermediate phase of reassigning customers to depots, with the aim of obtaining a high-quality solution in the final routing phase. Detection and reassignment of customers are based on a combination of misplaced-customer criterion and routing algorithms. The complexity of the algorithms used in each phase can be chosen by the decision-makers of the distribution problem, according to their needs and possibilities. In previous research, we studied the performance of the methodology using well-known routing algorithms and comparing the results obtained against a commercial solver, for small-size instances of the CMDVRP. In addition, we analysed the impact of including the intermediate phase of exploration in the methodology by means of a comparative study over ten large instances with different geographical characteristics. Considering the promising results obtained previously, we present here a more detailed version of the methodology, considering additional characteristics of the problem for the assignment and exploration phases. With this new version, we can improve the results obtained previously and solve MDVRP instances from the literature, in a competitive way. Finally, the benefits obtained from adding randomness to select the misplaced customers in the exploration phase will be shown.
Keywords
- VRP
- Logistics
- Optimization Models and Methods
Status: accepted
Back to the list of papers