This repository contains the Python implementation of the various heuristic methods described in the paper: "A Sum-of-Squares Heuristic for a Dynamic Vehicle Routing Problem".
The dataset folder includes a sample of 8 problem instances. The table below provides a summary of the characteristics of each instance and the number of customers served using the SoS insertion algorithm (with/without local search). The table also shows the lower bound (LB) and upper bound (UB) figures obtained using an exact model to provide the upper bound values.
| Instance |
m |
D |
DL |
SoS |
SoS with LS |
UB |
LB |
| instanceAUni.xy |
5 |
2 |
Uni |
28 |
30 |
52 |
49 |
| instanceBUni.xy |
5 |
4 |
Uni |
100 |
100 |
100 |
100 |
| instanceCUni.xy |
5 |
2 |
Uni |
29 |
30 |
33 |
33 |
| instanceDUni.xy |
5 |
4 |
Uni |
74 |
87 |
97 |
92 |
| instanceAExp.xy |
5 |
2 |
Exp |
47 |
61 |
82 |
77 |
| instanceBExp.xy |
5 |
4 |
Exp |
100 |
100 |
100 |
100 |
| instanceCExp.xy |
5 |
2 |
Exp |
25 |
25 |
32 |
32 |
| instanceDExp.xy |
5 |
4 |
Exp |
78 |
98 |
100 |
98 |
Below are the plots for each solution. For each problem instance, we illustrate two scenarios: one with the SoS insertion algorithm without any local search, and the other with the SoS insertion algorithm incorporating a local search that considers the SoS criterion as an objective.
| Without Local Search |
With Local Search |
 |
 |
| Without Local Search |
With Local Search |
 |
 |
| Without Local Search |
With Local Search |
 |
 |
| Without Local Search |
With Local Search |
 |
 |
| Without Local Search |
With Local Search |
 |
 |
| Without Local Search |
With Local Search |
 |
 |
| Without Local Search |
With Local Search |
 |
 |
| Without Local Search |
With Local Search |
 |
 |
Each problem instance follows the format below:
- The first line: Number of customers (always 100).
- The second line: ID of the depot and its coordinates.
Following that, there are 100 lines, each containing the following information for a customer: customer_ID X_coordinate Y_coordinate
