Discrete Optimization VRPTW

Links

• The project
• The report

Objectives

The Vehicle Routing Problem (VRP) is a complex challenge that arises in many domains requiring optimal management of logistic and transportation resources. It is an optimization problem aimed at determining the most efficient routes for a set of vehicles to serve a set of customers with specific constraints.

The goal of this project was therefore to solve this problem using different metaheuristics to obtain the best results.

Technologies Used

• Programming Languages: Java
• Metaheuristic Algorithms:
  • Tabu Search
  • Simulated Annealing
  • Gradient Descent

Work Done

To solve this problem, a code was developed. The code first allows creating random delivery routes and then displaying them via a graphical interface.

Then, different classes with different strategies and metaheuristics were implemented to analyze them.

Finally, a large number of tests were carried out in different conditions and with different metaheuristics to determine the best one (see the report for more details).

Conclusion

This project allowed me to learn more about solving complex optimization problems. One can think of the knapsack problem or the traveling salesman problem.

I could see that it was not possible to find the optimal solution to this kind of problem given the large number of solutions and the time it would take. Thus, the goal was to apply methods to find solutions that are good enough and close to the optimal solution.

I found it fascinating to solve a problem in this way and to think about the fact that in everyday situations or for business problems, concessions must be made. Indeed, sometimes finding the optimal solution to a problem is not necessarily necessary if you already have a good solution.

This project was very enriching. It was a first to have a project of this type where we had some freedom in the implementation and resolution of the problem. Being able to apply the concepts seen in class and test them on a problem related to the business context was really motivating, it pleased and interested me a lot.