An open vehicle routing problem with drivers’ satisfaction solved by a multi-objective evolutionary algorithm based on decomposition

Salamatbakhsh, Alireza; Tavakkoli-Moghaddam, Reza; Norouzi, Narges

An open vehicle routing problem with drivers’ satisfaction solved by a multi-objective evolutionary algorithm based on decomposition

Document Type : Research Paper

Authors

Alireza Salamatbakhsh ¹

Reza Tavakkoli-Moghaddam ²

Narges Norouzi ³

¹ Islamic Azad University, Science and Research Branch

² Professor, School of Industrial Engineering, College of Engineering, University of Tehran

³ University of Tehran

Abstract

In this paper, a new mathematical model is presented for an open vehicle routing problem (OVRP) that maximizes drivers’ satisfaction and minimizes a number of vehicles simultaneously. One of the new problems related to the VRP area is the OVRP that is a new variant of the VRP. In the real world, because of decreasing the related cost, the vehicles should return to the depot after serving the last customer’s location, as the OVRPs do. It is proven that the classic models in VRPs belong to the category of NP-hard problems; thus due to its complexity using exact methods in large-scale problems, a meta-heuristic method based on multi-objective evolutionary algorithm based on decomposition (MOEA/D) is proposed and the associated results are compared with the results obtained by a multi-objective particle swarm optimization (MOPSO) algorithm. The results show that the proposed MOEA/D outperforms the MOPSO. Finally, the conclusion and further research are provided.

Keywords

Open vehicle routing problem

Multi-objective evolutionary algorithm

Decomposition

Particle swarm optimization