Vehicle-Routing-Problem-with-ILP-and-SA

This project is the final project for the course "Numerical Methods-Principles, Algorithms and Applications"(00136540) at School of Mathematical Sciences, Peking University. It contains implementations of two algorithms to solve the Vehicle Routing Problem (VRP): Integer Linear Programming (ILP) and Simulated Annealing (SA). The project is structured into three main directories: CVRP_Simulated_Annealing, VRP_Simulated_Annealing and CVRP_Integer_Linear_Programming.

Directory Structure

• CVRP_Integer_Linear_Programming: Contains MATLAB scripts for the Capacitated Vehicle Routing Problem (CVRP) using Integer Linear Programming (ILP).
• CVRP_Simulated_Annealing: Contains MATLAB scripts for the Capacitated Vehicle Routing Problem (CVRP) using Simulated Annealing.
• VRP_Simulated_Annealing: Contains MATLAB scripts for the Vehicle Routing Problem (VRP) using Simulated Annealing.
• report: Contains the LaTeX source files for the project report.

Running the Code

To run the code, you need to have MATLAB or baltamatica(www.baltamatica.com) installed on your machine. Open the MATLAB scripts in the CVRP_Integer_Linear_Programming, CVRP_Simulated_Annealing or VRP_Simulated_Annealing directories and run them.

Report

The report provides a detailed explanation of the problem, the implemented algorithms, and the results. It is written in LaTeX and can be compiled using xe-bib-xe-xe recipe.

References

The project is based on the following papers:

• Baker, Barrie M and Ayechew, MA1951066. "A genetic algorithm for the vehicle routing problem". Computers & Operations Research, 30(5):787--800, 2003.
• Bi, Jieyi and Ma, Yining and Wang, Jiahai and Cao, Zhiguang and Chen, Jinbiao and Sun, Yuan and Chee, Yeow Meng. "Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation". Advances in Neural Information Processing Systems, 2022.
• Kara, Imdat and Bektas, Tolga. "Integer linear programming formulation of the generalized vehicle routing problem". Proc. of the 5-th EURO/INFORMS Joint International Meeting, pages 06--10. Citeseer Istanbul, 2003.
• Vincent, F Yu and Redi, AAN Perwira and Hidayat, Yosi Agustina and Wibowo, Oktaviyanto Jimat. "A simulated annealing heuristic for the hybrid vehicle routing problem". Applied Soft Computing, volume 53.

For more details, please refer to the report directory.