This is an algorithm that seeks to solve the MDVRPTW.
The GRASP version of this project for the MDVRP was published on Computational Science and Its Applications – ICCSA 2022: 22nd International Conference, Malaga, Spain, July 4–7, 2022.
Table of Contents
The Vehicle Routing Problem (VRP) is a known hard-to-solve combinatorial problem (NP-hard). In this project, we seek to solve the Multi Depot Vehicle Routing Problem with Time Windows (MDVRPTW).
We adopt the cluster-first route-second approach. For this, the customers are clustered considering each depot as the cluster center (each depot creates a cluster). Then the construction process is applied to generate solutions.
Currently, we use a randomized version of the Solomon I1 Insertion Heuristic as the constructive algorithm. The random decisions are administrated by the GRASP metaheuristic. After the construction process, a set of local search methods are applied. The local search can be intra-depot and inter-depot. The former considers each cluster as a complete problem and the latter considers all clusters to improve the solution. In this project, we consider both intra-depot and inter-depot local search methods.
The GRASP version of the project was published on Computational Science and Its Applications – ICCSA 2022: 22nd International Conference, Malaga, Spain, July 4–7, 2022. Full article.
We also aim to develop an Ant Colony Optimization algorithm, instead of GRASP, to solve the problem. Which is in progress...
For now, you can use the GRASP version.
If you use this code, please cite our article.
A set of clustering methods are utilized.
- [K-Means]
- [Urgencies] Giosa et al. [2]
First, you need an MDVRPTW problem instance, which you can get on VRP Libraries. We will list some libraries in which you can get them. We have the "instances" folder with Cordeuat and Vidal MDVRPTW instances, mostly for backup purposes but You can use them too!
You can also make your instance, but it needs to follow Cordeaut standards.
Python 3.6 or higher is required.
- Get the dependencies
python -m pip install -r requirements.txt
- Run the project
python main.py <FLAGS>
Here we describe the algorithm parameters.
main.py:
(obrigatory)
--instance: path to the MDVRPTW instance.
(default: None)
(optional)
--cluster: the cluster method to use.
(default: 'kmeans')
(options: 'kmeans', 'urgencies')- Example of usage:
python main.py --instance ./instances/cordeau-al-2001-mdvrptw/pr01.txt --cluster kmeans
Israel P. - israelpereira55@gmail.com
Project Link: https://github.com/israelpereira55/MDVRPTW
[1] Cordeau, Jean-François, Gilbert Laporte, and Anne Mercier. "A unified tabu search heuristic for vehicle routing problems with time windows." Journal of the Operational research society 52.8 (2001): 928-936.
[2] Giosa, I. D., I. L. Tansini, and I. O. Viera. "New assignment algorithms for the multi-depot vehicle routing problem." Journal of the operational research society 53.9 (2002): 977-984.