Constraint Relaxation for Multi-Objective Optimization in Vehicle Routing Problem

N. Mukai (Japan)


Selfish Routing, Braess’s Paradox, Route Optimization, and Multi-Agent Simulation.


In these years, an on-demand bus system is focused as a new convenience transportation system. The main feature of the system is to transport customers door-to-door in on line processing. However, it is difficult to find the optimal solution for the problem (i.e., assignment of demands and routing of vehicles) in a practical calculation time. In or der to solve the problem, we start from a known problem called “Vehicle Routing Problem (VRP)“. The main objec tive of VRP is to minimize traveling cost such as gas money for collecting all of packages. We adopt genetic algorithm to find the near optimal solution for the VRP. An objec tive function of our genetic algorithm includes not only the main objective but also a sub objective (e.g., cluster size of demands). The sub objective can improve the convergence speed of solutions in the early evolution stage. However, the over-fitting of the sub objective has a bad effect on the main objective in the final evolution stage. Therefore, we apply a relaxation method of the sub objective constraint in the final optimization stage. Finally, we report our ex perimental results to evaluate the effect of the constraint relaxation of the sub objective.

Important Links:

Go Back