Genetic algorithm improves delivery route planning without fixed start point

Node-Shift-Encoding Genetic Algorithm with fuzzy-enhanced reference tour to solve the bi-objective service-oriented TSP

Computational Engineering, Finance, and Science

Summary

This paper looks at a tricky problem of figuring out the best way to visit multiple service clients when the order matters and there’s no fixed starting location. The authors created a new approach to represent and solve this problem using a genetic algorithm that adapts over time with some fuzzy logic helping guide the process. They also modified existing math models to better fit situations where the first stop isn’t fixed, which is important when client order really matters. Testing on standard route planning examples shows their approach works better than older methods. This could help improve routes in delivery, manufacturing, or service work where order and client ranking are important.

What this means in practice

  • For logistics planners: Create delivery routes that prioritize client ranking without needing a fixed start point using the new genetic algorithm approach.
  • For manufacturing schedulers: Schedule service tasks and machine visits where the order of clients affects efficiency, benefiting from the improved tour modeling.

Authors

Souad Abdoune, Menouar Boulif

Abstract

The Travelling Salesman Problem (TSP) remains a key area of research in combinatorial optimization, with applications in logistics, manufacturing, and service delivery. This paper addresses a bi-objective service-oriented TSP in which the clients' ranks in the delivery path matter. Unlike conventional depot-based TSP formulations, the considered problem does not assume a distinguished depot or a fixed tour origin. To address this setting, we adapt the Miller--Tucker--Zemlin (MTZ)-based formulation and derive an original linearization of the resulting model, enabling its solution with off-the-shelf integer linear programming solvers. This adaptation avoids the rigid tour origin imposed by the conventional MTZ formulation, for which fixing the starting node does not affect the tour cost but can affect the objective in a customer-rank-sensitive TSP. To solve this problem, we present a Node-Shift-Encoding (NSE)-based Genetic Algorithm augmented with fuzzy reasoning to update the reference tour throughout the evolutionary process. Experimental evaluation on TSPLIB benchmarks demonstrates that the proposed method achieves improved performance compared with the classical NSE approach.
View PDFOpen arXiv