Data Driven VRP: A Neural Network Model to Learn Hidden Preferences for VRP

Authors Jayanta Mandi , Rocsildes Canoy , Víctor Bucarey , Tias Guns



PDF
Thumbnail PDF

File

LIPIcs.CP.2021.42.pdf
  • Filesize: 1.11 MB
  • 17 pages

Document Identifiers

Author Details

Jayanta Mandi
  • Data Analytics Laboratory, Vrije Universiteit Brussel, Belgium
Rocsildes Canoy
  • Data Analytics Laboratory, Vrije Universiteit Brussel, Belgium
Víctor Bucarey
  • Institute of Engineering Sciences, Universidad de O'Higgins, Rancagua, Chile
Tias Guns
  • Data Analytics Laboratory, Vrije Universiteit Brussel, Belgium
  • Department of Computer Science, KU Leuven, Belgium

Cite AsGet BibTex

Jayanta Mandi, Rocsildes Canoy, Víctor Bucarey, and Tias Guns. Data Driven VRP: A Neural Network Model to Learn Hidden Preferences for VRP. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.42

Abstract

The traditional Capacitated Vehicle Routing Problem (CVRP) minimizes the total distance of the routes under the capacity constraints of the vehicles. But more often, the objective involves multiple criteria including not only the total distance of the tour but also other factors such as travel costs, travel time, and fuel consumption. Moreover, in reality, there are numerous implicit preferences ingrained in the minds of the route planners and the drivers. Drivers, for instance, have familiarity with certain neighborhoods and knowledge of the state of roads, and often consider the best places for rest and lunch breaks. This knowledge is difficult to formulate and balance when operational routing decisions have to be made. This motivates us to learn the implicit preferences from past solutions and to incorporate these learned preferences in the optimization process. These preferences are in the form of arc probabilities, i.e., the more preferred a route is, the higher is the joint probability. The novelty of this work is the use of a neural network model to estimate the arc probabilities, which allows for additional features and automatic parameter estimation. This first requires identifying suitable features, neural architectures and loss functions, taking into account that there is typically few data available. We investigate the difference with a prior weighted Markov counting approach, and study the applicability of neural networks in this setting.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Planning and scheduling
Keywords
  • Vehicle routing
  • Neural network
  • Preference learning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Rocsildes Canoy and Tias Guns. Vehicle routing by learning from historical solutions. In Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Stamford, CT, USA, September 30 - October 4, 2019, Proceedings, volume 11802, pages 54-70. Springer, 2019. Google Scholar
  2. Vaida Ceikute and Christian S Jensen. Routing service quality-local driver behavior versus routing services. In 2013 IEEE 14th International Conference on Mobile Data Management, volume 1, pages 97-106. IEEE, 2013. Google Scholar
  3. George B Dantzig and John H Ramser. The truck dispatching problem. Management science, 6(1):80-91, 1959. Google Scholar
  4. Emir Demirovic, Peter J. Stuckey, James Bailey, Jeffrey Chan, Chris Leckie, Kotagiri Ramamohanarao, and Tias Guns. An investigation into prediction + optimisation for the knapsack problem. In Louis-Martin Rousseau and Kostas Stergiou, editors, Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 16th International Conference, CPAIOR 2019, Thessaloniki, Greece, June 4-7, 2019, Proceedings, volume 11494 of Lecture Notes in Computer Science, pages 241-257. Springer, 2019. Google Scholar
  5. Adam N Elmachtoub and Paul Grigas. Smart “predict, then optimize”. Management Science, 2021. Google Scholar
  6. Stefan Funke, Sören Laue, and Sabine Storandt. Deducing individual driving preferences for user-aware navigation. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 1-9, 2016. Google Scholar
  7. Klaus Greff, Rupesh Kumar Srivastava, Jan Koutník, Bas R. Steunebrink, and Jürgen Schmidhuber. LSTM: A search space odyssey. IEEE Trans. Neural Networks Learn. Syst., 28(10):2222-2232, 2017. Google Scholar
  8. Chenjuan Guo, Bin Yang, Jilin Hu, Christian S Jensen, and Lu Chen. Context-aware, preference-based vehicle routing. The VLDB Journal, pages 1-22, 2020. Google Scholar
  9. LLC Gurobi Optimization. Gurobi optimizer reference manual, 2020. URL: http://www.gurobi.com.
  10. Xiangpei Hu, Zheng Wang, Minfang Huang, and Amy Z. Zeng. A computer-enabled solution procedure for food wholesalers' distribution decision in cities with a circular transportation infrastructure. Computers & Operations Research, 36(7):2201-2209, 2009. Google Scholar
  11. Nicolas Jozefowiez, Frédéric Semet, and El-Ghazali Talbi. Multi-objective vehicle routing problems. European journal of operational research, 189(2):293-309, 2008. Google Scholar
  12. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL: http://arxiv.org/abs/1412.6980.
  13. Christophe Lecluyse, Tom Van Woensel, and Herbert Peremans. Vehicle routing with stochastic time-dependent travel times. 4OR, 7(4):363-377, 2009. Google Scholar
  14. Tzong-Ru Lee and Ji-Hwa Ueng. A study of vehicle routing problems with load-balancing. International Journal of Physical Distribution & Logistics Management, 1999. Google Scholar
  15. Julia Letchner, John Krumm, and Eric Horvitz. Trip router with individualized preferences (trip): incorporating personalization into route planning. In IAAI'06 Proceedings of the 18th conference on Innovative applications of artificial intelligence - Volume 2, pages 1795-1800, 2006. Google Scholar
  16. Min Lin, Qiang Chen, and Shuicheng Yan. Network in network. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. Google Scholar
  17. Chun Kai Ling, Fei Fang, and J. Zico Kolter. What game are we playing? end-to-end learning in normal and extensive form games. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 396-402. ijcai.org, 2018. Google Scholar
  18. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pages 8024-8035, 2019. Google Scholar
  19. Yong Peng and Xiaofeng Wang. Research on a vehicle routing schedule to reduce fuel consumption. In 2009 International Conference on Measuring Technology and Mechatronics Automation, volume 3, pages 825-827, 2009. Google Scholar
  20. Marin Vlastelica Pogancic, Anselm Paulus, Vít Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020. Google Scholar
  21. J. David Schaffer. Multiple objective optimization with vector evaluated genetic algorithms. In Proceedings of the 1st International Conference on Genetic Algorithms, pages 93-100, 1985. Google Scholar
  22. Tomer Toledo, Yichen Sun, Katherine Rosa, Moshe Ben-Akiva, Kate Flanagan, Ricardo Sanchez, and Erika Spissu. Decision-making process and factors affecting truck routing. In Freight Transport Modelling. Emerald Group Publishing Limited, 2013. Google Scholar
  23. P Toth and D Vigo. The family of vehicle routing problem. Vehicle Routing: Problems, Methods, and Applications, pages 1-23, 2014. Google Scholar
  24. Po-Wei Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6545-6554, 2019. Google Scholar
  25. Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1658-1665, 2019. Google Scholar
  26. Yiyong Xiao, Qiuhong Zhao, Ikou Kaku, and Yuchun Xu. Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers & Operations Research, 39(7):1419-1431, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail