Abstract
This paper addresses the Vehicle Routing Problem with Service Time Customization (VRPTW-STC), which is an extension of the classic Vehicle Routing Problem with Time Window (VRPTW). In VRPTW-STC, the decision maker tries to find an optimum solution with the smallest fleet size, the lowest travelling distance as well as the largest total service time of all customers. The objective to enlarge each customer’s service time obviously conflicts with the need of reducing both changeable and fixed transport costs, i.e. travelling distance and fleet size. At the same time, the routing plan must meet the time window constraint and the vehicle capacity constraint. To solve this problem, we designed a Multi Ant System (MAS) based hybrid heuristic algorithm inspired by to decompose a multi-objective problem into several single objective ones. Then, Ant Colony Optimization (ACO) algorithms are applied to every single-objective problem. A unique global best solution is maintained to record the current best solution. The global best solution will be updated when a new feasible solution found by any ACO dominate current global best solution. Several local search algorithms are also incorporated into MAS to help improve the solution quality. Solomon’s benchmark tests are used to test the effectiveness of the proposed algorithm. The computation experiment results show that our proposed MAS based hybrid heuristic algorithm performs better than typical existing algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Calvete, H.I., Galé, C., Oliveros, M.J., Sánchez-Valverde, B.: A goal programming approach to vehicle routing problems with soft time windows. Eur. J. Oper. Res. 177(3), 1720–1733 (2007)
Beheshti, A.K., Hejazi, S.R.: A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window. Inf. Sci. 316(C), 598–615 (2015)
Lin, J.J.: A GA-based multi-objective decision making for optimal vehicle transportation. J. Inf. Sci. Eng. 24(1), 237–260 (2008)
Gupta, R., Singh, B., Pandey, D.: Multi-objective fuzzy vehicle routing problem: a case study. Int. J. Contemp. Math. Sci. 5(29), 1439–1454 (2010)
Gupta, A., Nagarajan, V., Ravi, R.: Approximation algorithms for VRP with stochastic demands. Oper. Res. 60(1), 123–127 (2012)
Shukla, N., Choudhary, A.K., Prakash, P.K.S., Fernandes, K.J., Tiwari, M.K.: Algorithm portfolios for logistics optimization considering stochastic demands and mobility allowance. Int. J. Prod. Econ. 141(1), 146–166 (2013)
Peng, J., Shang, G., Liu, H.: A hybrid intelligent algorithm for vehicle routing models with fuzzy travel times. Computational Intelligence. LNCS (LNAI), vol. 4114, pp. 965–976. Springer, Heidelberg (2006). https://doi.org/10.1007/978-3-540-37275-2_122
Sarhadi, H., Ghoseiri, K.: An ant colony system approach for fuzzy traveling salesman problem with time windows. Int. J. Adv. Manuf. Technol. 50(9–12), 1203–1215 (2010)
Zarandi, M.F., Hemmati, A.: Capacitated location-routing problem with time windows under uncertainty. Knowl.-Based Syst. 37(2), 480–489 (2013)
Wen, L., Eglese, R.: Minimum cost VRP with time-dependent speed data and congestion charge. Comput. Oper. Res. 56, 41–50 (2015)
Kok, A.L., Hans, E.W., Schutten, J.M.J.: Vehicle routing under time-dependent travel times: the impact of congestion avoidance. Comput. Oper. Res. 39(5), 910–918 (2012)
Kuo, Y.: Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Comput. Ind. Eng. 59(1), 157–165 (2010)
Hooshmand, F., Mirhassani, S.A.: Time dependent green VRP with alternative fuel powered vehicles. Energy Syst. (2018). https://doi.org/10.1007/s12667-018-0283-y
Huang, Y., Zhao, L., Woensel, T.V., Gross, J.P.: Time-dependent vehicle routing problem with path flexibility. Transp. Res. Part B Methodol. 95, 169–195 (2017)
Ray, S., Soeanu, A., Berger, J., Debbabi, M.: The multi-depot split-delivery vehicle routing problem: model and solution algorithm. Knowl.-Based Syst. 71(1), 238–265 (2014)
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254–265 (1987)
Acknowledgments
This work is supported by the National Natural Science Foundation of China (Grant numbers: 71701203, 71690233).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Wang, Y., Xing, L. (2018). A Multi Ant System Based Hybrid Heuristic Algorithm for Vehicle Routing Problem with Service Time Customization. In: Qiao, J., et al. Bio-inspired Computing: Theories and Applications. BIC-TA 2018. Communications in Computer and Information Science, vol 951. Springer, Singapore. https://doi.org/10.1007/978-981-13-2826-8_36
Download citation
DOI: https://doi.org/10.1007/978-981-13-2826-8_36
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-2825-1
Online ISBN: 978-981-13-2826-8
eBook Packages: Computer ScienceComputer Science (R0)