Multiobjective quantum evolutionary algorithm for the vehicle routing problem with customer satisfaction. (English) Zbl 1264.90025

Summary: The multiobjective vehicle routing problem considering customer satisfaction (MVRPCS) involves the distribution of orders from several depots to a set of customers over a time window. This paper presents a self-adaptive grid multi-objective quantum evolutionary algorithm (MOQEA) for the MVRPCS, which takes into account customer satisfaction as well as travel costs. The degree of customer satisfaction is represented by proposing an improved fuzzy due-time window, and the optimization problem is modeled as a mixed integer linear program. In the MOQEA, nondominated solution set is constructed by the Challenge Cup rules. Moreover, an adaptive grid is designed to achieve the diversity of solution sets; that is, the number of grids in each generation is not fixed but is automatically adjusted based on the distribution of the current generation of nondominated solution set. In the study, the MOQEA is evaluated by applying it to classical benchmark problems. Results of numerical simulation and comparison show that the established model is valid and the MOQEA is effective for MVRPCS.


90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
90C29 Multi-objective and goal programming
68T05 Learning and adaptive systems in artificial intelligence


Full Text: DOI


[1] P. Toth and D. Vigo, The Vehicle Routing Problem, vol. 9 of SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa, USA, 2002. · Zbl 1248.97004 · doi:10.1137/1.9780898718515
[2] G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Management Science, vol. 6, pp. 80-91, 1959. · Zbl 0995.90560 · doi:10.1287/mnsc.6.1.80
[3] W. Huang and S. Chen, “Epidemic metapopulation model with traffic routing in scale-free networks,” Journal of Statistical Mechanics, vol. 2011, no. 12, Article ID P12004, 19 pages, 2011. · doi:10.1088/1742-5468/2011/12/P12004
[4] M. Li, W. Zhao, and S. Chen, “MBm-based scalings of traffic propagated in internet,” Mathematical Problems in Engineering, vol. 2011, Article ID 389803, 21 pages, 2011. · Zbl 1210.68027 · doi:10.1155/2011/389803
[5] S. Y. Chen, H. Tong, Z. Wang, S. Liu, M. Li, and B. Zhang, “Improved generalized belief propagation for vision processing,” Mathematical Problems in Engineering, vol. 2011, Article ID 416963, 12 pages, 2011. · Zbl 1202.94026 · doi:10.1155/2011/416963
[6] C. H. Jiang, S. G. Dai, and Y. H. Hu, “Hybrid genetic algorithm for capacitated vehicle routing problem,” Computer Integrated Manufacturing Systems, vol. 13, no. 10, pp. 2047-2052, 2007 (Chinese).
[7] C. Prins, “A simple and effective evolutionary algorithm for the vehicle routing problem,” Computers & Operations Research, vol. 31, no. 12, pp. 1985-2002, 2004. · Zbl 1100.90504 · doi:10.1016/S0305-0548(03)00158-8
[8] P. Reiter and W. J. Gutjahr, “Exact hybrid algorithms for solving a bi-objective vehicle routing problem,” Central European Journal of Operations Research, vol. 20, no. 1, pp. 19-43, 2012. · Zbl 1245.90010 · doi:10.1007/s10100-010-0158-3
[9] S. P. Anbuudayasankar, K. Ganesh, S. C. Lenny Koh, and Y. Ducq, “Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls,” Expert Systems with Applications, vol. 39, pp. 2296-2305, 2012.
[10] S. C. Hong and Y. B. Park, “Heuristic for bi-objective vehicle routing with time window constraints,” International Journal of Production Economics, vol. 62, no. 3, pp. 249-258, 1999. · doi:10.1016/S0925-5273(98)00250-3
[11] E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach,” IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, pp. 257-271, 1999.
[12] A. Lim and F. Wang, “A smoothed dynamic tabu search embedded GRASP for m-VRPTW,” in Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI ’04), pp. 704-708, November 2004.
[13] K. C. Tan, Y. H. Chew, and L. H. Lee, “A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows,” Computational Optimization and Applications, vol. 34, no. 1, pp. 115-151, 2006. · Zbl 1111.90022 · doi:10.1007/s10589-005-3070-3
[14] A. Garcia-Najera and J. A. Bullinaria, “An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows,” Computers & Operations Research, vol. 38, no. 1, pp. 287-300, 2011. · Zbl 1231.90087 · doi:10.1016/j.cor.2010.05.004
[15] P. Badeau, F. Guertin, M. Gendreau, J. Y. Potvin, and E. Taillard, “A parallel tabu search heuristic for the vehicle routing problem with time windows,” Transportation Research C, vol. 5, no. 2, pp. 109-122, 1997. · Zbl 0886.90070
[16] K. C. Tan, L. H. Lee, Q. L. Zhu, and K. Ou, “Heuristic methods for vehicle routing problem with time windows,” Artificial Intelligence in Engineering, vol. 15, no. 3, pp. 281-295, 2001. · doi:10.1016/S0954-1810(01)00005-X
[17] J. Berger and M. Barkaoui, “A parallel hybrid genetic algorithm for the vehicle routing problem with time windows,” Computers & Operations Research, vol. 31, no. 12, pp. 2037-2053, 2004. · Zbl 1100.90503 · doi:10.1016/S0305-0548(03)00163-1
[18] A. Le Bouthillier and T. G. Crainic, “A cooperative parallel meta-heuristic for the vehicle routing problem with time windows,” Computers and Operations Research, vol. 32, no. 7, pp. 1685-1708, 2005. · Zbl 1074.90006 · doi:10.1016/j.cor.2003.11.023
[19] G. B. Alvarenga, G. R. Mateus, and G. de Tomi, “A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows,” Computers and Operations Research, vol. 34, no. 6, pp. 1561-1584, 2007. · Zbl 1163.90357 · doi:10.1016/j.cor.2005.07.025
[20] R. Cheng and M. Gen, “Vehicle routing problem with fuzzy due-time using genetic algorithms,” Japanese Journal of Fuzzy Theory and Systems, vol. 7, no. 5, pp. 1050-1061, 1995.
[21] R. Cheng and M. Gen, “Fuzzy vehicle routing and scheduling problem using genetic algorithm,” in Genetic Algorithms and Soft Computing, F. Herrera and J. Verdegay, Eds., pp. 683-709, Springer, 1996.
[22] S. Wen, W. Zheng, J. Zhu, X. Li, and S. Chen, “Elman fuzzy adaptive control for obstacle avoidance of mobile robots using hybrid force/position incorporation,” IEEE Transactions on Systems, Man and Cybernetics C, vol. 42, no. 4, pp. 603-608, 2012. · doi:10.1109/TSMCC.2011.2157682
[23] S. Y. Chen, J. Zhang, H. Zhang, N. M. Kwok, and Y. F. Li, “Intelligent lighting control for vision-based robotic manipulation,” IEEE Transactions on Industrial Electronics, vol. 59, no. 8, pp. 3254-33263, 2012.
[24] C. Cattani, “Shannon wavelets for the solution of integrodifferential equations,” Mathematical Problems in Engineering, vol. 2010, Article ID 408418, 22 pages, 2010. · Zbl 1191.65174 · doi:10.1155/2010/408418
[25] J. Y. Zhang, Y. H. Guo, and J. Li, “Research of multi-objective fuzzy vehicle scheduling problem based on satisfaction of customers,” Journal of the China Railway Society, vol. 25, no. 2, pp. 15-17, 2003 (Chinese).
[26] Y. J. Jia, Optimal algorithm research of vehicle scheduling problem [Ph.D. thesis], Shanghai Jiaotong University, 2004.
[27] B. Wu, Particle swarm optimization for velaicle routing problem and its application [Ph.D. thesis], Zhejiang University of Technology, 2008.
[28] J.-J. Lin, “A GA-based multi-objective decision making for optimal vehicle transportation,” Journal of Information Science and Engineering, vol. 24, no. 1, pp. 237-260, 2008.
[29] C. H. Wang and C. H. Li, “Optimization of an established multi-objective delivering problem by an improved hybrid algorithm,” Expert Systems with Applications, vol. 38, no. 4, pp. 4361-4367, 2011. · doi:10.1016/j.eswa.2010.09.105
[30] K.-H. Han and J.-H. Kim, “Quantum-inspired evolutionary algorithm for a class of combinatorial optimization,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 6, pp. 580-593, 2002. · doi:10.1109/TEVC.2002.804320
[31] M. Fonseca Carlos and J. Peter Fleming, “Genetic algorithm for multiobjecetive optimization: formulation, dicussion and generalization,” in Proceeding of the 5th International Conference on Genetic Algorithm, pp. 416-423, 1993.
[32] S. Chen, Y. Zheng, C. Cattani, and W. Wang, “Modeling of biological intelligence for SCM system optimization,” Computational and Mathematical Methods in Medicine, Article ID 769702, 10 pages, 2012. · Zbl 1235.90022 · doi:10.1155/2012/769702
[33] S. Y. Chen and Y. F. Li, “Automatic Sensor Placement for Model-Based Robot Vision,” IEEE Transactions on Systems, Man, and Cybernetics B, vol. 34, no. 1, pp. 393-408, 2004. · doi:10.1109/TSMCB.2003.817031
[34] Z. Jinhua, Multi-Objective Evolutionary Algorithm and Its Application, Science Press, Beijing, China, 2007.
[35] J. Knowles and D. W. Corne, “The pareto archived evolution strategy: a new baseline algorithm foe pareto multiobjective optimisation,” in Proceeding of the Congress of Evolutionary Computation, pp. 98-105, 1999.
[36] D. W. Corne, D. K. Joshua, and J. O. Martin, “The pareto envelope-based selection algorithm for multiobjective optimization,” in Proceeding of the Parallel Problem Solving from Nature VI Conference, pp. 839-848, Springer, 2000.
[37] A. Narayanan and M. Moore, “Quantum-inspired genetic algorithms,” in Proceedings of IEEE International Conference on Evolutionary Computation (ICEC ’96), pp. 61-66, May 1996.
[38] J. C. Bean, “Genetic alogrithms and random keys for sequedcing and optimization,” ORSA Journal on Computing, vol. 6, pp. 154-160, 1994. · Zbl 0807.90060 · doi:10.1287/ijoc.6.2.154
[39] Z. Jingling, Z. Yanwei, et al., “A hybrid quantum-inspired evolutionary algorithm for capacitated vehicle routing problem,” in Proceedings Advanced Intelligent Computing Theories and Applications, vol. 5226, pp. 31-38, Springer, Berlin, Germany, 2008.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.