An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows |
| |
| Institution: | 1. CIRRELT – Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, École de Technologie Supérieure de Montréal, Canada;2. CIRRELT – Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, and Département de mathématiques et génie industriel, École Polytechnique de Montréal, Canada;3. CIRRELT – Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, and Département de management et de technologie, Université du Québec à Montréal, Canada;4. GERAD – Group for Research in Decision Analysis, and Département de mathématiques et génie industriel, École Polytechnique de Montréal, Canada;5. Département de génie de la construction, École de Technologie Supérieure de Montréal, Canada;1. Ecole des Mines de Saint-Etienne and UMR CNRS 6158 LIMOS CMP Georges Charpak F-13541 Gardanne, France;2. LIMOS, Institut Supérieur d’Informatique de Modélisation et leurs Applications, ISIMA, Campus des Czeaux, Aubire Cedex, France;1. State Key Laboratory of Synthetic Automation for Process Industries, Department of Intelligent Systems Engineering, Northeastern University, Shenyang, 110819, P.R. China;2. Department of Industrial and Manufacturing Systems Engineering, the University of Hong Kong, Pokfulam Road, Hong Kong |
| |
| Abstract: | The solution of routing problems with soft time windows has valuable practical applications. Soft time window solutions are needed when: (a) the number of routes needed for hard time windows exceeds the number of available vehicles, (b) a study of cost-service tradeoffs is required, or (c) the dispatcher has qualitative information regarding the relative importance of hard time-window constraints across customers. This paper proposes a new iterative route construction and improvement algorithm to solve vehicle routing problems with soft time windows. Due to its modular and hierarchical design, the solution algorithm is intuitive and able to accommodate general cost and penalty functions. Experimental results indicate that the average run time performance is of order O(n2). The solution quality and computational time of the new algorithm has been compared against existing results on benchmark problems. The presented algorithm has improved thirty benchmark problem solutions for the vehicle routing problems with soft time windows. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
