Improving of the Clarke and Wright’s Heuristic for Solving Multiobjective Vehicles Routing Problem

---

Résumé

In this paper, we propose a new multiobjective model for the Capacitated Vehicle Routing Problem with a single depot. On one hand, the model aims to optimize multiple conflicting objectives, such as minimizing the total travel distance and reducing the number of vehicles used. On the other hand, we develop a heuristic approach to effectively solve the problem. The Vehicle Routing Problem is one of the most widely studied combinatorial optimization problems, particularly in logistics and supply chain management. It encompasses numerous variants and is classified as NP-hard, making exact methods impractical for large-scale instances. Our proposed heuristic combines two well-known principles: the Hungarian method, typically used for solving assignment problems, and the Clarke-Wright savings algorithm, commonly applied in VRP contexts. This hybridization operates in two main stages: First, the Hungarian method is employed to identify the shortest paths within the cost matrix, thereby facilitating efficient pairing of nodes. Second, the Clarke-Wright savings principle is applied to construct low-cost vehicle routes. This combined approach enables us to achieve two key objectives: minimizing the size of the vehicle fleet and reducing the total distance traveled. A comparative study based on several benchmark instances demonstrates that the proposed method produces high-quality solutions, validating its effectiveness and potential for practical application.

Mots-clés

Combinatorial-Optimization, Transportation-problems, Vehicle-routing, Efficient-solutions, Multiobjective-optimization.