{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T14:36:11Z","timestamp":1772807771945,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T00:00:00Z","timestamp":1693526400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T00:00:00Z","timestamp":1696982400000},"content-version":"vor","delay-in-days":40,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ANID Fondecyt Iniciacion","award":["11220864"],"award-info":[{"award-number":["11220864"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate a<jats:italic>learning<\/jats:italic>decision support system for vehicle routing, where the routing engine learns implicit preferences that human planners have when manually creating route plans (or<jats:italic>routings<\/jats:italic>). The goal is to use these learned<jats:italic>subjective<\/jats:italic>preferences on top of the distance-based<jats:italic>objective<\/jats:italic>criterion in vehicle routing systems. This is an alternative to the practice of distinctively formulating a custom vehicle routing problem (VRP) for every company with its own routing requirements. Instead, we assume the presence of past vehicle routing solutions over similar sets of customers, and learn to make similar choices. The learning approach is based on the concept of learning a Markov model, which corresponds to a probabilistic transition matrix, rather than a deterministic distance matrix. This nevertheless allows us to use existing arc routing VRP software in creating the actual routings, and to optimize over both distances and preferences at the same time. For the learning, we explore different schemes to construct the probabilistic transition matrix that can co-evolve with changing preferences over time. Our results on randomly generated instances and on a use-case with a small transportation company show that our method is able to generate results that are close to the manually created solutions, without needing to characterize all constraints and sub-objectives explicitly. Even in the case of changes in the customer sets, our approach is able to find solutions that are closer to the actual routings than when using only distances, and hence, solutions that require fewer manual changes when transformed into practical routings.<\/jats:p>","DOI":"10.1007\/s10601-023-09363-2","type":"journal-article","created":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T14:03:12Z","timestamp":1697032992000},"page":"363-396","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Learn and route: learning implicit preferences for vehicle routing"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1810-082X","authenticated-orcid":false,"given":"Rocsildes","family":"Canoy","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3043-8404","authenticated-orcid":false,"given":"V\u00edctor","family":"Bucarey","sequence":"additional","affiliation":[]},{"given":"Jayanta","family":"Mandi","sequence":"additional","affiliation":[]},{"given":"Tias","family":"Guns","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,11]]},"reference":[{"issue":"4","key":"9363_CR1","doi-asserted-by":"publisher","first-page":"119","DOI":"10.5121\/ijdkp.2013.3408","volume":"3","author":"RR Ade","year":"2013","unstructured":"Ade, R. R., & Deshmukh, P. R. (2013). Methods for incremental learning: a survey. International Journal of Data Mining & Knowledge Management Process, 3(4), 119.","journal-title":"International Journal of Data Mining & Knowledge Management Process"},{"issue":"8","key":"9363_CR2","doi-asserted-by":"publisher","first-page":"152","DOI":"10.3390\/a12080152","volume":"12","author":"SR Ait Haddadene","year":"2019","unstructured":"Ait Haddadene, S. R., Labadie, N., & Prodhon, C. (2019). Bicriteria Vehicle Routing Problem with Preferences and Timing Constraints in Home Health Care Services. Algorithms, 12(8), 152.","journal-title":"Algorithms"},{"key":"9363_CR3","doi-asserted-by":"publisher","first-page":"175","DOI":"10.2307\/1575226","volume":"4","author":"C Ames","year":"1989","unstructured":"Ames, C. (1989). The Markov process as a compositional model: A survey and tutorial. Leonardo, 4, 175\u2013187.","journal-title":"Leonardo"},{"issue":"5","key":"9363_CR4","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00779-003-0240-0","volume":"7","author":"D Ashbrook","year":"2003","unstructured":"Ashbrook, D., & Starner, T. (2003). Using GPS to learn significant locations and predict movement across multiple users. Personal and Ubiquitous Computing, 7(5), 275\u2013286.","journal-title":"Personal and Ubiquitous Computing"},{"key":"9363_CR5","doi-asserted-by":"crossref","unstructured":"Beldiceanu, N., & Simonis, H. (2011). \u201cA constraint seeker: Finding and ranking global constraints from examples.\u201d In: International conference on principles and practice of constraint programming. Springer, pp. 12\u201326","DOI":"10.1007\/978-3-642-23786-7_4"},{"key":"9363_CR6","doi-asserted-by":"crossref","unstructured":"Beldiceanu, N., & Simonis, H. (2012). \u201cA model seeker: Extracting global constraint models from positive examples.\u201d In: International conference on principles and practice of constraint programming. Springer, pp. 141\u2013157","DOI":"10.1007\/978-3-642-33558-7_13"},{"key":"9363_CR7","unstructured":"Bello, I., Pham, H., Le, Q. V., Norouzi, M., & Bengio, S. (2017). Neural combinatorial optimization with reinforcement learning. https:\/\/openreview.net\/forum?id=rJY3vK9eg"},{"key":"9363_CR8","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.artint.2015.08.001","volume":"244","author":"C Bessiere","year":"2017","unstructured":"Bessiere, C., Koriche, F., Lazaar, N., & O\u2019Sullivan, B. (2017). Constraint acquisition. Artificial Intelligence, 244, 315\u2013342.","journal-title":"Artificial Intelligence"},{"issue":"2","key":"9363_CR9","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/2666003","volume":"47","author":"J Caceres-Cruz","year":"2015","unstructured":"Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., & Juan, A. A. (2015). Rich vehicle routing problem: Survey. ACM Computing Surveys (CSUR), 47(2), 32.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"9363_CR10","doi-asserted-by":"crossref","unstructured":"Canoy, R., & Guns, T. (2019). \u201cVehicle routing by learning from historical solutions.\u201d In: International conference on principles and practice of constraint programming. Springer, pp. 54\u201370","DOI":"10.1007\/978-3-030-30048-7_4"},{"key":"9363_CR11","doi-asserted-by":"crossref","unstructured":"Ceikute, V., & Jensen, C. S. (2013). \u201cRouting service quality-local driver behavior versus routing services.\u201d In: 2013 IEEE 14th international conference on mobile data management. Vol. 1. IEEE, pp. 97\u2013106","DOI":"10.1109\/MDM.2013.20"},{"key":"9363_CR12","doi-asserted-by":"crossref","unstructured":"Chang, K.-P., Wei, L.-Y., Yeh, M.-Y., & Peng, W.-C. (2011). \u201cDiscovering personalized routes from trajectories.\u201d In: Proceedings of the 3rd ACM SIGSPATIAL international workshop on location-based social networks, pp. 33\u201340","DOI":"10.1145\/2063212.2063218"},{"issue":"3","key":"9363_CR13","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1016\/j.ejor.2021.03.031","volume":"295","author":"L Chen","year":"2021","unstructured":"Chen, L., Chen, Y., & Langevin, A. (2021). An inverse optimization approach for a capacitated vehicle routing problem. European Journal of Operational Research, 295(3), 1087\u20131098.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"9363_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1006\/csla.1999.0128","volume":"13","author":"SF Chen","year":"1999","unstructured":"Chen, S. F., & Goodman, J. (1999). An empirical study of smoothing techniques for language modeling. Computer Speech & Language, 13(4), 359\u2013394.","journal-title":"Computer Speech & Language"},{"issue":"2","key":"9363_CR15","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1111\/j.2517-6161.1961.tb00424.x","volume":"23","author":"DR Cox","year":"1961","unstructured":"Cox, D. R. (1961). Prediction by exponentially weighted moving averages and related methods. Journal of the Royal Statistical Society: Series B (Methodological), 23(2), 414\u2013422.","journal-title":"Journal of the Royal Statistical Society: Series B (Methodological)"},{"issue":"1","key":"9363_CR16","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"GB Dantzig","year":"1959","unstructured":"Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80\u201391.","journal-title":"Management Science"},{"key":"9363_CR17","volume-title":"HEV charge\/discharge control system based on navigation information","author":"Y Deguchi","year":"2004","unstructured":"Deguchi, Y., Kuroda, K., Shouji, M., & Kawabe, T. (2004). HEV charge\/discharge control system based on navigation information. SAE Technical Paper: Tech. rep."},{"key":"9363_CR18","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A. V., Goldszmidt, M., Krumm, J., Talwar, K., & Werneck, R. F. (2015). \u201cNavigation made personal: Inferring driving preferences from gps traces.\u201d In: Proceedings of the 23rd SIGSPATIAL international conference on advances in geographic information Systems, pp. 1\u20139","DOI":"10.1145\/2820783.2820808"},{"key":"9363_CR19","doi-asserted-by":"crossref","unstructured":"Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., & Rousseau, L.-M. (2018). \u201cLearning heuristics for the tsp by policy gradient.\u201d In: Integration of constraint programming, artificial intelligence, and operations research: 15th international conference, CPAIOR 2018, Delft, The Netherlands, June 26\u201329, 2018, Proceedings 15. Springer, pp. 170\u2013181","DOI":"10.1007\/978-3-319-93031-2_12"},{"key":"9363_CR20","doi-asserted-by":"publisher","first-page":"71","DOI":"10.3389\/frobt.2017.00071","volume":"4","author":"P Dragone","year":"2018","unstructured":"Dragone, P., Teso, S., & Passerini, A. (2018). Constructive preference elicitation. Frontiers in Robotics and AI, 4, 71.","journal-title":"Frontiers in Robotics and AI"},{"issue":"1\u20132","key":"9363_CR21","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s12159-012-0080-2","volume":"5","author":"M Drexl","year":"2012","unstructured":"Drexl, M. (2012). Rich vehicle routing in theory and practice. Logistics Research, 5(1\u20132), 47\u201363.","journal-title":"Logistics Research"},{"issue":"4","key":"9363_CR22","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1145\/2523813","volume":"46","author":"J Gama","year":"2014","unstructured":"Gama, J., \u017dliobait\u0117, I., Bifet, A., Pechenizkiy, M., & Bouchachia, A. (2014). A survey on concept drift adaptation. ACM Computing Surveys (CSUR), 46(4), 44.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"9363_CR23","doi-asserted-by":"crossref","unstructured":"Guo, C., Yang, B., Hu, J., Jensen, C. S., & Chen, L. (2020). Context-aware, preference-based vehicle routing. The VLDB Journal, 29, 1149\u20131170.","DOI":"10.1007\/s00778-020-00608-7"},{"issue":"11","key":"9363_CR24","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1287\/mnsc.13.11.821","volume":"13","author":"PJ Harrison","year":"1967","unstructured":"Harrison, P. J. (1967). Exponential smoothing and short-term sales forecasting. Management Science, 13(11), 821\u2013842.","journal-title":"Management Science"},{"key":"9363_CR25","doi-asserted-by":"crossref","unstructured":"Irnich, S., Toth, P., & Vigo, D. (2014). \u201cChapter 1: The family of vehicle routing problems.\u201d In: Vehicle routing: problems, methods, and applications, second edition. SIAM, pp. 1\u201333","DOI":"10.1137\/1.9781611973594.ch1"},{"issue":"164","key":"9363_CR26","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1093\/mind\/XLI.164.409","volume":"41","author":"W E Johnson","year":"1932","unstructured":"Johnson, W. E. (1932). Probability: The deductive and inductive problems. Mind, 41(164), 409\u2013423.","journal-title":"Mind"},{"key":"9363_CR27","unstructured":"Kool, W., Van Hoof, H., & Welling, M. (2019). \u201cAttention, Learn to Solve Routing Problems!\u201d In: International conference on learning representations. https:\/\/openreview.net\/forum?id=ByxBFsRqYm"},{"key":"9363_CR28","doi-asserted-by":"crossref","unstructured":"Krumm, J. (2008). \u201cA Markov Model for Driver Turn Prediction.\u201d In: SAE 2008 world congress. Lloyd L. Withrow Distinguished Speaker Award","DOI":"10.4271\/2008-01-0195"},{"issue":"8","key":"9363_CR29","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1002\/nav.20261","volume":"54","author":"G Laporte","year":"2007","unstructured":"Laporte, G. (2007). What you should know about the vehicle routing problem. Naval Research Logistics (NRL), 54(8), 811\u2013819.","journal-title":"Naval Research Logistics (NRL)"},{"key":"9363_CR30","unstructured":"Letchner, J., Krumm, J., & Horvitz, E. (2006). \u201cTrip router with individualized preferences (trip): Incorporating personalization into route planning.\u201d In: AAAI, pp. 1795\u20131800"},{"issue":"1","key":"9363_CR31","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01580665","volume":"10","author":"G P McCormick","year":"1976","unstructured":"McCormick, G. P. (1976). Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems. Mathematical Programming, 10(1), 147\u2013175.","journal-title":"Mathematical Programming"},{"key":"9363_CR32","doi-asserted-by":"crossref","unstructured":"Mor, A., & Speranza, M. G. (2020). \u201cVehicle routing problems over time: a survey.\u201d In: 4OR, pp. 1\u201321","DOI":"10.1007\/s10288-020-00433-2"},{"key":"9363_CR33","unstructured":"Nazari M, Oroojlooy A, Snyder L, & Tak\u00e1c M. (2018). \u201cReinforcement Learning for Solving the Vehicle Routing Problem.\u201d In: Advances in Neural Information Processing Systems. Ed. by Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., & Garnett, R. Vol. 31. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2018\/file\/9fb4651c05b2ed70fba5afe0b039a550-Paper.pdf"},{"key":"9363_CR34","doi-asserted-by":"crossref","unstructured":"Picard-Cantin, \u00c9., Bouchard, M., Quimper, C.-G., & Sweeney, J. (2016). \u201cLearning parameters for the sequence constraint from solutions.\u201d In: International conference on principles and practice of constraint programming. Springer, pp. 405\u2013420","DOI":"10.1007\/978-3-319-44953-1_26"},{"issue":"4","key":"9363_CR35","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/0305-0548(93)90081-S","volume":"20","author":"J-Y Potvin","year":"1993","unstructured":"Potvin, J.-Y., Dufour, G., & Rousseau, J.-M. (1993). Learning vehicle dispatching with linear programming models. Computers & Operations Research, 20(4), 371\u2013380.","journal-title":"Computers & Operations Research"},{"issue":"1","key":"9363_CR36","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10732-006-9001-3","volume":"13","author":"K S\u00f6rensen","year":"2007","unstructured":"S\u00f6rensen, K. (2007). Distance measures based on the edit distance for permutation-type representations. Journal of Heuristics, 13(1), 35\u201347.","journal-title":"Journal of Heuristics"},{"key":"9363_CR37","unstructured":"Veli\u010dkovi\u0107, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2018). \u201cGraph Attention Networks.\u201d In: International conference on learning representations. https:\/\/openreview.net\/forum?id=rJXMpikCZ"},{"key":"9363_CR38","unstructured":"Vinyals, O., Fortunato, M., & Jaitly, N. (2015). \u201cPointer Networks.\u201d In: Advances in neural information processing systems. Ed. by Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., & Garnett, R. Vol. 28. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2015\/file\/29921001f2f04bd3baee84a12e98098f-Paper.pdf"},{"key":"9363_CR39","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/j.procs.2015.07.305","volume":"53","author":"X Wang","year":"2015","unstructured":"Wang, X., Ma, Y., Di, J., Murphey, Y. L., Qiu, S., Kristinsson, J., Meyer, J., Tseng, F., & Feldkamp, T. (2015). Building efficient probability transition matrix using machine learning from big data for personalized route prediction. Procedia Computer Science, 53, 284\u2013291.","journal-title":"Procedia Computer Science"},{"key":"9363_CR40","doi-asserted-by":"crossref","unstructured":"Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Reinforcement Learning, 5\u201332.","DOI":"10.1007\/978-1-4615-3618-5_2"},{"key":"9363_CR41","doi-asserted-by":"crossref","unstructured":"Yang, B., Guo, C., Jensen, C. S., Kaul, M., & Shang, S. (2014). \u201cStochastic skyline route planning under time-varying uncertainty.\u201d In: 2014 IEEE 30th international conference on data engineering. IEEE, pp. 136\u2013147","DOI":"10.1109\/ICDE.2014.6816646"},{"issue":"2","key":"9363_CR42","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00778-015-0378-1","volume":"24","author":"B Yang","year":"2015","unstructured":"Yang, B., Guo, C., Yu, M., & Jensen, C. S. (2015). Toward personalized, context-aware routing. The VLDB Journal, 24(2), 297\u2013318.","journal-title":"The VLDB Journal"},{"key":"9363_CR43","doi-asserted-by":"crossref","unstructured":"Yang, S. B., & Yang, B. (2019). \u201cPathRank: A Multi-Task Learning Framework to Rank Paths in Spatial Networks.\u201d arXiv preprint arXiv:1907.04028","DOI":"10.1109\/ICDE48307.2020.00225"},{"key":"9363_CR44","doi-asserted-by":"crossref","unstructured":"Ye, N., Wang, Z.-Q., Malekian, R., Lin, Q., & Wang, R.-C. (2015). A method for driving route predictions based on hidden Markov model. Mathematical Problems in Engineering, 2015","DOI":"10.1155\/2015\/824532"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09363-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-023-09363-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09363-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T16:25:43Z","timestamp":1730305543000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-023-09363-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["9363"],"URL":"https:\/\/doi.org\/10.1007\/s10601-023-09363-2","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9]]},"assertion":[{"value":"8 September 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}