A Quantum Evolutionary Algorithm for the Vehicle Routing Problem with Single-sided Time Window Setting

Abstract

Customer service level is of prime importance in today competitive world and has various dimensions with delivery quality being one of the most important ones. Delivery quality has several parameters such as deliver time window options, time window size, etc. In this paper we focus on one of these parameters, namely time window setting. It has a direct impact upon customer satisfaction and business profit. On the other hand, delivery time windows affect routing and distribution costs. Generally, in the routing operation, time windows have been determined by customers or distributer and are considered as input parameters for the vehicle routing problem with time window (VRPTW) model. In this paper, a mathematical model is proposed for the integration of these two decisions in other words, in the present model, time window setting decisions are integrated with routing decisions. Then a column generation approach is employed to obtain the lower bounds of problems and to solve the problems, a quantum algorithm is proposed. Finally, the computational results of some instances are reported and the results of these approaches are compared. The results demonstrate the effectiveness of the quantum algorithm in solving this problem.

Keywords

• Time window setting
• Vehicle routing problem
• Column generation
• Quantum algorithm