{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T05:23:59Z","timestamp":1790832239697,"version":"4.1.0"},"reference-count":39,"publisher":"SAGE Publications","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIC"],"published-print":{"date-parts":[[2021,2,15]]},"abstract":"<jats:p>On-Demand Transport (ODT) systems have attracted increasing attention in recent years. Traditional centralized dispatching can achieve optimal solutions, but NP-Hard complexity makes it unsuitable for online and dynamic problems. Centralized and decentralized heuristics can achieve fast, feasible solution at run-time with no guarantee on the quality. Starting from a feasible not optimal solution, we present in this paper a new solution model (ORNInA) consisting of two parallel coordination processes. The first one is a decentralized insertion-heuristic based algorithm to build vehicle schedules in order to solve a particular case of the dynamic Dial-A-Ride-Problem (DARP) as an ODT system, in which vehicles communicate via Vehicle-to-vehicle communication (V2V) and make decentralized decisions. The second coordination scheme is a continuous optimization process namely Pull-demand protocol, based on combinatorial auctions, in order to improve the quality of the global solution achieved by decentralized decision at run-time by exchanging resources between vehicles (k-opt). In its simplest implementation, k is set to 1 so that vehicles can exchange only one resource at a time. We evaluate and analyze the promising results of our contributed techniques on synthetic data for taxis operating in Saint-\u00c9tienne city, against a classical decentralized greedy approach and a centralized one that uses a classical mixed-integer linear program (MILP) solver.<\/jats:p>","DOI":"10.3233\/aic-201579","type":"journal-article","created":{"date-parts":[[2021,1,5]],"date-time":"2021-01-05T12:13:55Z","timestamp":1609848835000},"page":"37-53","source":"Crossref","is-referenced-by-count":11,"title":["ORNInA: A decentralized, auction-based multi-agent coordination in ODT systems"],"prefix":"10.1177","volume":"34","author":[{"given":"Alaa","family":"Daoud","sequence":"first","affiliation":[{"name":"Laboratoire Hubert Curien UMR CNRS 5516, Institut Henri Fayol, Mines Saint \u00c9tienne, Saint \u00c9tienne, France. E-mails:\u00a0alaa.daoud@emse.fr,\u00a0flavien.balbo@emse.fr"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Flavien","family":"Balbo","sequence":"additional","affiliation":[{"name":"Laboratoire Hubert Curien UMR CNRS 5516, Institut Henri Fayol, Mines Saint \u00c9tienne, Saint \u00c9tienne, France. E-mails:\u00a0alaa.daoud@emse.fr,\u00a0flavien.balbo@emse.fr"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paolo","family":"Gianessi","sequence":"additional","affiliation":[{"name":"LIMOS UMR CNRS 6158, Institut Henri Fayol, Mines Saint \u00c9tienne, Saint \u00c9tienne, France. E-mail:\u00a0paolo.gianessi@emse.fr"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gauthier","family":"Picard","sequence":"additional","affiliation":[{"name":"ONERA\/DTIS, Universit\u00e9 de Toulouse, 2 Avenue Edouard Belin, 31055, Toulouse Cedex 4, France. E-mail:\u00a0gauthier.picard@onera.fr"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","reference":[{"key":"10.3233\/AIC-201579_ref1","unstructured":"E.T.S.I.\u00a0(ETSI), Intelligent Transport Systems (ITS);Access layer specification for Intelligent Transport Systems operating in the 5 GHz frequency band, Technical Report, 2012."},{"issue":"9","key":"10.3233\/AIC-201579_ref2","doi-asserted-by":"publisher","first-page":"1450","DOI":"10.1016\/j.trb.2011.05.017","article-title":"Dynamic ride-sharing: A simulation study in metro Atlanta","volume":"45","author":"Agatz","year":"2011","journal-title":"Transportation Research Part B: Methodological"},{"key":"10.3233\/AIC-201579_ref3","unstructured":"C.\u00a0Bellini, G.\u00a0Dellepiane and C.\u00a0Quaglierini, The demand responsive transport services: Italian approach, Transaction on the Built Environment 64 (2003), 10."},{"key":"10.3233\/AIC-201579_ref4","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1016\/j.trb.2019.03.004","article-title":"The electric autonomous dial-a-ride problem","volume":"122","author":"Bongiovanni","year":"2019","journal-title":"Transportation Research Part B: Methodological"},{"key":"10.3233\/AIC-201579_ref5","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s41604-019-00014-5","article-title":"A dial-a-ride problem using private vehicles and alternative nodes","author":"Brevet","year":"2019","journal-title":"Journal on Vehicle Routing Algorithms"},{"issue":"3","key":"10.3233\/AIC-201579_ref6","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1287\/trsc.1030.0046","article-title":"Efficient insertion heuristics for vehicle routing and scheduling problems","volume":"38","author":"Campbell","year":"2004","journal-title":"Transportation science"},{"key":"10.3233\/AIC-201579_ref9","first-page":"37","article-title":"Issues in multiagent resource allocation","volume":"30","author":"Chevaleyre","year":"2006","journal-title":"Informatica"},{"issue":"2","key":"10.3233\/AIC-201579_ref10","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1111\/1475-3995.00256","article-title":"Modeling and optimizing dynamic dial-a-ride problems","volume":"8","author":"Colorni","year":"2001","journal-title":"International transactions in operational research"},{"issue":"1","key":"10.3233\/AIC-201579_ref11","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10479-007-0170-8","article-title":"The dial-a-ride problem: Models and algorithms","volume":"153","author":"Cordeau","year":"2007","journal-title":"Annals of Operations Research"},{"key":"10.3233\/AIC-201579_ref12","doi-asserted-by":"crossref","unstructured":"J.-F.\u00a0Cordeau, G.\u00a0Laporte, J.-Y.\u00a0Potvin and M.W.P.\u00a0Savelsbergh, Chapter\u00a07 transportation on demand, in: Handbooks in Operations Research and Management Science, C.\u00a0Barnhart and G.\u00a0Laporte, eds, Transportation, Vol.\u00a014, Elsevier, 2007, pp.\u00a0429\u2013466, http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0927050706140074.","DOI":"10.1016\/S0927-0507(06)14007-4"},{"key":"10.3233\/AIC-201579_ref13","doi-asserted-by":"crossref","unstructured":"J.-F.\u00a0Cordeau, G.\u00a0Laporte, M.W.P.\u00a0Savelsbergh and D.\u00a0Vigo, Chapter\u00a06 vehicle routing, in: Handbooks in Operations Research and Management Science, Vol.\u00a014, Elsevier, 2007, pp.\u00a0367\u2013428, https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0927050706140062. ISBN 978-0-444-51346-5.","DOI":"10.1016\/S0927-0507(06)14006-2"},{"issue":"3","key":"10.3233\/AIC-201579_ref14","doi-asserted-by":"publisher","first-page":"1605","DOI":"10.1016\/j.ejor.2005.02.038","article-title":"A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem","volume":"175","author":"Coslovich","year":"2006","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"10.3233\/AIC-201579_ref15","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/1345037.1345039","article-title":"An overview of combinatorial auctions","volume":"7","author":"Cramton","year":"2007","journal-title":"ACM SIGecom Exchanges"},{"key":"10.3233\/AIC-201579_ref16","doi-asserted-by":"crossref","unstructured":"P.\u00a0Danassis, A.\u00a0Filos-Ratsikas and B.\u00a0Faltings, Anytime heuristic for weighted matching through altruism-inspired behavior, in: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, Macao, China, 2019, pp.\u00a0215\u2013222, https:\/\/www.ijcai.org\/proceedings\/2019\/31. ISBN 978-0-9992411-4-1.","DOI":"10.24963\/ijcai.2019\/31"},{"key":"10.3233\/AIC-201579_ref17","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.trc.2016.03.008","article-title":"Vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communication in a heterogeneous wireless network \u2013 performance evaluation","volume":"68","author":"Dey","year":"2016","journal-title":"Transportation Research Part C: Emerging Technologies"},{"key":"10.3233\/AIC-201579_ref19","doi-asserted-by":"crossref","unstructured":"M.\u00a0El Falou, M.\u00a0Itmi, S.\u00a0El Falou and A.\u00a0Cardon, On demand transport system\u2019s approach as a multi-agent planning problem, in: 2014 International Conference on Advanced Logistics and Transport (ICALT), IEEE, 2014, pp.\u00a053\u201358.","DOI":"10.1109\/ICAdLT.2014.6864081"},{"key":"10.3233\/AIC-201579_ref20","unstructured":"A.\u00a0Glaschenko, A.\u00a0Ivaschenko, G.\u00a0Rzevski and P.\u00a0Skobelev, Multi-agent real time scheduling system for taxi companies, in: AAMAS 2009, p.\u00a08."},{"key":"10.3233\/AIC-201579_ref21","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1016\/j.procs.2015.05.162","article-title":"Agent based modelling for simulating taxi services","volume":"52","author":"Grau","year":"2015","journal-title":"Procedia Computer Science"},{"issue":"2","key":"10.3233\/AIC-201579_ref22","doi-asserted-by":"publisher","first-page":"159","DOI":"10.12720\/jtle.1.2.159-163","article-title":"Agent based modeling for simulation of taxi services","volume":"1","author":"Grau","year":"2013","journal-title":"Journal of Traffic and Logistics Engineering"},{"issue":"2","key":"10.3233\/AIC-201579_ref23","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1287\/trsc.2018.0837","article-title":"Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem","volume":"53","author":"Gschwind","year":"2019","journal-title":"Transportation Science"},{"issue":"1","key":"10.3233\/AIC-201579_ref24","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s12469-008-0006-1","article-title":"The integrated dial-a-ride problem","volume":"1","author":"H\u00e4ll","year":"2009","journal-title":"Public Transport"},{"issue":"2","key":"10.3233\/AIC-201579_ref25","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s12532-009-0004-6","article-title":"General k-opt submoves for the Lin\u2013Kernighan TSP heuristic","volume":"1","author":"Helsgaun","year":"2009","journal-title":"Mathematical Programming Computation"},{"issue":"3","key":"10.3233\/AIC-201579_ref26","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0191-2615(86)90020-2","article-title":"A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows","volume":"20","author":"Jaw","year":"1986","journal-title":"Transportation Research Part B: Methodological"},{"key":"10.3233\/AIC-201579_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012426297-3.50027-8"},{"key":"10.3233\/AIC-201579_ref28","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262033428.003.0013"},{"issue":"1","key":"10.3233\/AIC-201579_ref29","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02031946","article-title":"A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives","volume":"60","author":"Madsen","year":"1995","journal-title":"Annals of Operations Research"},{"issue":"3","key":"10.3233\/AIC-201579_ref30","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1287\/opre.45.3.365","article-title":"Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints","volume":"45","author":"Mingozzi","year":"1997","journal-title":"Operations Research"},{"key":"10.3233\/AIC-201579_ref31","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.trc.2015.02.024","article-title":"A distributed VNS algorithm for optimizing dial-a-ride problems in large-scale scenarios","volume":"54","author":"Muelas","year":"2015","journal-title":"Transportation Research Part C: Emerging Technologies"},{"key":"10.3233\/AIC-201579_ref33","doi-asserted-by":"publisher","DOI":"10.3166\/RIA.32.223-247"},{"issue":"1\u20132","key":"10.3233\/AIC-201579_ref34","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/s12469-016-0128-9","article-title":"The integrated dial-a-ride problem with timetabled fixed route service","volume":"9","author":"Posada","year":"2017","journal-title":"Public Transport"},{"issue":"4","key":"10.3233\/AIC-201579_ref35","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1080\/01441647.2015.1017749","article-title":"Simulating demand-responsive transportation: A review of agent-based approaches","volume":"35","author":"Ronald","year":"2015","journal-title":"Transport Reviews"},{"issue":"1","key":"10.3233\/AIC-201579_ref36","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1287\/trsc.29.1.17","article-title":"The general pickup and delivery problem","volume":"29","author":"Savelsbergh","year":"1995","journal-title":"Transportation Science"},{"key":"10.3233\/AIC-201579_ref38","doi-asserted-by":"crossref","unstructured":"W.\u00a0Shen and C.\u00a0Lopes, Managing autonomous mobility on demand systems for better passenger experience, in: PRIMA 2015: Principles and Practice of Multi-Agent Systems, Vol.\u00a09387, Springer, 2015, pp.\u00a020\u201335, arXiv:1507.02563 [cs].","DOI":"10.1007\/978-3-319-25524-8_2"},{"key":"10.3233\/AIC-201579_ref39","first-page":"532","volume-title":"Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations","author":"Shoham","year":"2009"},{"issue":"2","key":"10.3233\/AIC-201579_ref40","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1287\/opre.35.2.254","article-title":"Algorithms for the vehicle routing and scheduling problems with time window constraints","volume":"35","author":"Solomon","year":"1987","journal-title":"Operations Research"},{"key":"10.3233\/AIC-201579_ref42","unstructured":"TRB\u2019s Transit Cooperative Research Program (TCRP) Report 124, Guidebook for Measuring, Assessing, and Improving Performance of Demand-Response Transportation, Vol.\u00a0124, Transportation Research Board, Washington, DC, 2008."},{"key":"10.3233\/AIC-201579_ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2020.101199"},{"key":"10.3233\/AIC-201579_ref44","doi-asserted-by":"publisher","DOI":"10.1145\/2330784.2330832"},{"key":"10.3233\/AIC-201579_ref45","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1016\/j.trc.2016.09.002","article-title":"Generic model for resource allocation in transportation. Application to urban parking management","volume":"71","author":"Zargayouna","year":"2016","journal-title":"Transportation Research Part C: Emerging Technologies"}],"container-title":["AI Communications"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/AIC-201579","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T18:27:57Z","timestamp":1777400877000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.medra.org\/servlet\/aliasResolver?alias=iospress&doi=10.3233\/AIC-201579"}},"subtitle":["Online Rescheduling with Neighborhood exchange, based on insertion heuristic and Auctions"],"editor":[{"given":"Marin","family":"Lujak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]},{"given":"Ivana","family":"Dusparic","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]},{"given":"Franziska","family":"Kl\u00fcgl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]},{"given":"Giuseppe","family":"Vizzari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2021,2,15]]},"references-count":39,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.3233\/aic-201579","relation":{},"ISSN":["1875-8452","0921-7126"],"issn-type":[{"value":"1875-8452","type":"electronic"},{"value":"0921-7126","type":"print"}],"subject":[],"published":{"date-parts":[[2021,2,15]]}}}