Advanced search
Publication Cover
International Journal of Systems Science: Operations & Logistics Volume 10, 2023 - Issue 1
Submit an article Journal homepage
1,842
Views
3
CrossRef citations to date
0
Altmetric
Research Article

Hybrid fleet capacitated vehicle routing problem with flexible Monte–Carlo Tree search

Carmen Barlettaa The Surrey Business School, University of Surrey, Guildford, Surrey, UK;b Department of Mechanical Engineering Sciences, Connected Autonomous Vehicles Lab, University of Surrey, Guildford, Surrey, UKORCID Iconhttps://orcid.org/0000-0003-3954-9802View further author information
ORCID Icon,
Wolfgang Garna The Surrey Business School, University of Surrey, Guildford, Surrey, UKCorrespondence[email protected]
ORCID Iconhttps://orcid.org/0000-0003-2278-8997View further author information
ORCID Icon,
Christopher Turnera The Surrey Business School, University of Surrey, Guildford, Surrey, UKORCID Iconhttps://orcid.org/0000-0003-2812-3312View further author information
ORCID Icon &
Saber Fallahb Department of Mechanical Engineering Sciences, Connected Autonomous Vehicles Lab, University of Surrey, Guildford, Surrey, UKORCID Iconhttps://orcid.org/0000-0002-1298-1040View further author information
ORCID Icon
Article: 2102265 | Received 29 Mar 2022, Accepted 11 Jul 2022, Published online: 03 Aug 2022

References

  • Abdo, A., Edelkamp, S., & Lawo, M. (2016). Nested rollout policy adaptation for optimizing vehicle selection in complex VRPs. In IEEE 41st conference on local computer networks workshops (pp. 213–221). IEEE.
  • Amjadian, A., & Gharaei, A. (2021). An integrated reliable five-level closed-loop supply chain with multi-stage products under quality control and green policies: Generalised outer approximation with exact penalty. International Journal of Systems Science: Operations & Logistics, 1–21. https://doi.org/10.1080/23302674.2021.1919336
  • Applegate, D. L., Bixby, R. E., Chvatal, V., & Cook, W. J. (2011). The traveling salesman problem: A computational study, Princeton Series in Applied Mathematics, Princeton University Press.
  • Arneson, B., Hayward, R. B., & Henderson, P. (2010). Monte Carlo Tree search in Hex. IEEE Transactions on Computational Intelligence and AI in Games, 2(4), 251–258. https://doi.org/10.1109/TCIAIG.2010.2067212
  • Askari, R., Sebt, M. V., & Amjadian, A. (2021). A multi-product EPQ model for defective production and inspection with single machine, and operational constraints: Stochastic programming approach. Communications in Computer and Information Science, 1458, 161–193. https://doi.org/10.1007/978-3-030-89743-7
  • Baldacci, R., Toth, P., & Vigo, D. (2010, February). Exact algorithms for routing problems under vehicle capacity constraints. Annals of Operations Research, 175(1), 213–245. https://doi.org/10.1007/s10479-009-0650-0
  • Beresneva, E., & Avdoshin, S. (2018). Analysis of mathematical formulations of capacitated vehicle routing problem and methods for their solution. In Proceedings of the institute for system programming (Vol. 30, pp. 233–250). [Proceedings of the Institute for System Programming of the Russian Academy of Sciences]
  • Brandão, J. (2011). A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem. Computers & Operations Research, 38(1), 140–151. https://doi.org/10.1016/j.cor.2010.04.008
  • Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., & Colton, S. (2012). A survey of Monte Carlo Tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43. https://doi.org/10.1109/TCIAIG.2012.2186810
  • Cazenave, T. (2009). Nested Monte-Carlo search. In Proceedings of the 21st international joint conference on artificial intelligence (pp. 456–461). Morgan Kaufmann Publishers Inc.
  • Cazenave, T., Lucas, J. Y., Kim, H., & Triboulet, T. (2020). Monte Carlo vehicle routing. In ATT at ECAI 2020.
  • Chaslot, G. M. B., Winands, M. H., & Herik, H. (2008). Parallel Monte-Carlo Tree search. In International conference on computers and games (pp. 60–71). Springer.
  • Choi, E., & Tcha, D. W. (2007). A column generation approach to the heterogeneous fleet vehicle routing problem. Computers & Operations Research, 34(7), 2080–2095. https://doi.org/10.1016/j.cor.2005.08.002
  • Comert, S. E., Yazgan, H. R., Kır, S., & Yener, F. (2018). A cluster first-route second approach for a capacitated vehicle routing problem: A case study. International Journal of Procurement Management, 11(4), 399–419. https://doi.org/10.1504/IJPM.2018.092766
  • Coulom, R. (2009). The Monte-Carlo revolution in Go. In The Japanese-French frontiers of science symposium (JFFoS 2008) (Vol. 115).
  • Croes, G. A. (1958). A method for solving Traveling-Salesman problems. Operations Research, 6(6), 791–812. https://doi.org/10.1287/opre.6.6.791
  • Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2), 266–288. https://doi.org/10.1287/opre.5.2.266
  • Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–91. https://doi.org/10.1287/mnsc.6.1.80
  • De Cauwer, C., Verbeke, W., Coosemans, T., Faid, S., & Van Mierlo, J. (2017). A data-driven method for energy consumption prediction and energy-efficient routing of electric vehicles in real-world conditions. Energies, 10(5), 608. https://doi.org/10.3390/en10050608
  • De Jaegere, N., Defraeye, M., & Van Nieuwenhuyse, I. (2014). The vehicle routing problem: State of the art classification and review (FEB Research Report KBI_1415).
  • Edelkamp, S., Gath, M., Greulich, C., Humann, M., Herzog, O., & Lawo, M. (2016). Monte-Carlo Tree search for logistics. In Commercial transport (pp. 427–440). Springer.
  • Erdoğan, S., & Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 48(1), 100–114. https://doi.org/10.1016/j.tre.2011.08.001
  • European Environment Agency (2016). Electric vehicles and the energy sector -- impacts on europe's future emissions. Retrieved May 16, 2022, https://www.eea.europa.eu/publications/electric-vehicles-and-the-energy/
  • Fern, A., & Lewis, P. (2011, March). Ensemble Monte-Carlo planning: An empirical study. In Twenty-First International Conference on Automated Planning and Scheduling.
  • Garn, W. (2020). Closed form distance formula for the balanced multiple travelling salesmen. ArXiV preprint arXiv:2001.07749.
  • Garn, W. (2021). Balanced dynamic multiple travelling salesmen: Algorithms and continuous approximations. Computers & Operations Research, 136, Article 105509. https://doi.org/10.1016/j.cor.2021.105509
  • Geetha, S., Poonthalir, G., & Vanathi, P. (2009). Improved K-Means algorithm for capacitated clustering problem. INFOCOMP Journal of Computer Science, 8(4), 52–59.
  • Gharaei, A., Amjadian, A., & Shavandi, A. (2021). An integrated reliable four-level supply chain with multi-stage products under shortage and stochastic constraints. International Journal of Systems Science: Operations & Logistics, 1–22. https://doi.org/10.1080/23302674.2021.1958023
  • Gharaei, A., Hoseini Shekarabi, S. A., & Karimi, M. (2021). Optimal lot-sizing of an integrated EPQ model with partial backorders and re-workable products: An outer approximation. International Journal of Systems Science: Operations & Logistics, 1–17. https://doi.org/10.1080/23302674.2021.2015007
  • Gharaei, A., Hoseini Shekarabi, S. A., Karimi, M., Pourjavad, E., & Amjadian, A. (2021). An integrated stochastic EPQ model under quality and green policies: Generalised cross decomposition under the separability approach. International Journal of Systems Science: Operations & Logistics, 8(2), 119–131. https://doi.org/10.1080/23302674.2019.1656296
  • Gharaei, A., Karimi, M., & Hoseini Shekarabi, S. A. (2021). Vendor-managed inventory for joint replenishment planning in the integrated qualitative supply chains: Generalised benders decomposition under separability approach. International Journal of Systems Science: Operations & Logistics, 1–15. https://doi.org/10.1080/23302674.2021.1962428
  • Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533–549. https://doi.org/10.1016/0305-0548(86)90048-1
  • Goeke, D., & Schneider, M. (2015). Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research, 245(1), 81–99. https://doi.org/10.1016/j.ejor.2015.01.049
  • Hashimoto, J., Kishimoto, A., Yoshizoe, K., & Ikeda, K. (2012). Accelerated UCT and its application to two-player games. In H. J. van den Herik and A. Plaat (Eds.), Advances in computer games (pp. 1–12). Springer Berlin Heidelberg.
  • Hiermann, G., Hartl, R. F., Puchinger, J., & Vidal, T. (2019). Routing a mix of conventional, plug-in hybrid, and electric vehicles. European Journal of Operational Research, 272(1), 235–248. https://doi.org/10.1016/j.ejor.2018.06.025
  • Justesen, N., Mahlmann, T., Risi, S., & Togelius, J. (2017). Playing multiaction adversarial games: Online evolutionary planning versus tree search. IEEE Transactions on Games, 10(3), 281–291. https://doi.org/10.1109/TCIAIG.2017.2738156
  • Kartal, B., Nunes, E., Godoy, J., & Gini, M. (2016, July). Monte Carlo Tree search with branch and bound for multi-robot task allocation.
  • Kizilateş, G., & Nuriyeva, F. (2013). On the nearest neighbor algorithms for the traveling salesman problem. In Advances in computational science, engineering and information technology (pp. 111–118). Springer International Publishing.
  • Kolmogorov, V. (2009). Blossom V: A new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, 1(1), 43–67. https://doi.org/10.1007/s12532-009-0002-8
  • Lai, D. S., Demirag, O. C., & Leung, J. M. (2016). A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E: Logistics and Transportation Review, 86, 32–52. https://doi.org/10.1016/j.tre.2015.12.001
  • Laporte, G., Nobert, Y., & Desrochers, M. (1985). Optimal routing under capacity and distance restrictions. Operations Research, 33(5), 1050–1073. https://doi.org/10.1287/opre.33.5.1050
  • Lebeau, P., De Cauwer, C., Van Mierlo, J., Macharis, C., Verbeke, W., & Coosemans, T. (2015, January). Conventional, hybrid, or electric vehicles: Which technology for an urban distribution centre?. The Scientific World Journal, 2015. https://doi.org/10.1155/2015/302867
  • Li, F., Golden, B., & Wasil, E. (2007). A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem. Computers & Operations Research, 34(9), 2734–2742. https://doi.org/10.1016/j.cor.2005.10.015
  • Lubosch, M., Kunath, M., & Winkler, H. (2018). Industrial scheduling with Monte Carlo Tree search and machine learning. Procedia CIRP, 72, 1283–1287. https://doi.org/10.1016/j.procir.2018.03.171
  • Malinen, M. I., & Fränti, P. (2014). Balanced K-means for clustering. In Joint IAPR international workshops on statistical techniques in pattern recognition (SPR) and structural and syntactic pattern recognition (SSPR) (pp. 32–41). Springer.
  • Mańdziuk, J. (2010). Knowledge-free and learning-based methods in intelligent game playing (Vol. 276).
  • Mańdziuk, J. (2011). Towards cognitively plausible game playing systems. IEEE Computational Intelligence Magazine, 6(2), 38–51. https://doi.org/10.1109/MCI.2011.940626
  • Mańdziuk, J., & Nejman, C. (2015, June). UCT-based approach to capacitated vehicle routing problem. In Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science) (Vol. 9120, pp. 679–690). Springer.
  • Meliani, Y., Hani, Y., Elhaq, S. L., & El Mhamedi, A. (2019). A developed Tabu search algorithm for heterogeneous fleet vehicle routing problem. IFAC-PapersOnLine, 52(13), 1051–1056. https://doi.org/10.1016/j.ifacol.2019.11.334
  • Penna, P. H. V., Subramanian, A., & Ochi, L. S. (2013). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19(2), 201–232. https://doi.org/10.1007/s10732-011-9186-y
  • Perron, L., & Furnon, V. (2019). OR-Tools. Retrieved May 16, 2022, https://developers.google.com/optimization/.
  • Sbai, I., & Krichen, S. (2022, March). Vehicle routing problems with loading constraints: An overview of variants and solution methods. In Optimization and machine learning (pp. 1–23). John Wiley & Sons.
  • Schneider, M., Stenger, A., & Goeke, D. (2014, March). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48(4), 500–520. https://doi.org/10.1287/trsc.2013.0490
  • Silver, D., Huang, A., Maddison, C., Guez, A., Sifre, L., Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., & Hassabis, D. (2016, January). Mastering the game of Go with deep neural networks and tree search. Nature, 529, 484–489. https://doi.org/10.1038/nature16961
  • Soejima, Y., Kishimoto, A., & Watanabe, O. (2011, January). Evaluating root parallelization in Go. IEEE Transactions on Computational Intelligence and AI in Games, 2(4), 278–287. https://doi.org/10.1109/TCIAIG.2010.2096427
  • Subramanian, A., Penna, P. H. V., Uchoa, E., & Ochi, L. S. (2012). A hybrid algorithm for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research, 221(2), 285–295. https://doi.org/10.1016/j.ejor.2012.03.016
  • Sutton, R. S., & Barto, A. G (2018). Reinforcement learning: An introduction. A Bradford Book.
  • Taleizadeh, A. A., Safaei, A. Z., Bhattacharya, A., & Amjadian, A. (2022, March). Online peer-to-peer lending platform and supply chain finance decisions and strategies. Annals of Operations Research, 1–31. https://doi.org/10.1007/s10479-022-04648-w
  • Tanabe, Y., Yoshizoe, K., & Imai, H. (2009). A study on security evaluation methodology for image-based biometrics authentication systems. In 2009 IEEE 3rd international conference on biometrics: Theory, applications, and systems (pp. 1–6). IEEE.
  • Tong, B. K. B., Ma, C. M., & Sung, C. W. (2011). A Monte-Carlo approach for the endgame of Ms. Pac-Man. In IEEE conference on computational intelligence and games (pp. 9–15). IEEE.
  • Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., & Subramanian, A. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3), 845–858. https://doi.org/10.1016/j.ejor.2016.08.012
  • United States Environmental Protection Agency (2020). Inventory of U.S. Greenhouse Gas Emissions and Sinks: 1990–2018. Retrieved May 16, 2022, https://www.epa.gov/ghgemissions/inventory-us-greenhouse-gas-emissions-and-sinks-1990–2018.
  • Venables, W. N., & Ripley, B. D (2013). Modern applied statistics with s-plus. Springer Science & Business Media.
  • Vidal, T. (2022, April). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers & Operations Research, 140, Article 105643. https://doi.org/10.1016/j.cor.2021.105643
  • Yuan, Y., Cattaruzza, D., Ogier, M., & Semet, F. (2020). A note on the lifted Miller–Tucker–Zemlin subtour elimination constraints for routing problems with time windows. Operations Research Letters, 48(2), 167–169. https://doi.org/10.1016/j.orl.2020.01.008
  • Zhou, Y., Grygorash, O., & Hain, T. F. (2011). Clustering with minimum spanning trees. International Journal on Artificial Intelligence Tools, 20(01), 139–177. https://doi.org/10.1142/S0218213011000061
  • Zhuang, J., Chu, S. C., Hu, C. C., Liao, L., & Pan, J. S. (2022, March). Advanced phasmatodea population evolution algorithm for capacitated vehicle routing problem. Journal of Advanced Transportation, 2022, 1–20. https://doi.org/10.1155/2022/9241112

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.