ORNInA: A decentralized,auction-based multi-agent coordination in ODT systems

Abstract

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-Étienne city, against a classical decentralized greedy approach and a centralized one that uses a classical mixed-integer linear program (MILP) solver.

Keywords

On-demand transport coordination decentralized optimization combinatorial auctions

Get full access to this article

View all access options for this article.

References

E.T.S.I. (ETSI), Intelligent Transport Systems (ITS);Access layer specification for Intelligent Transport Systems operating in the 5 GHz frequency band, Technical Report, 2012.

N.A.H.

Agatz,

A.L.

Erera,

M.W.P.

Savelsbergh and

Wang, Dynamic ride-sharing: A simulation study in metro Atlanta, Transportation Research Part B: Methodological45(9) (2011), 1450–1464, Select Papers from the 19th ISTTT, http://www.sciencedirect.com/science/article/pii/S0191261511000671. doi:10.1016/j.trb.2011.05.017.

Bellini,

Dellepiane and

Quaglierini, The demand responsive transport services: Italian approach, Transaction on the Built Environment64 (2003), 10.

Bongiovanni,

Kaspi and

Geroliminis, The electric autonomous dial-a-ride problem, Transportation Research Part B: Methodological122 (2019), 436–456. doi:10.1016/j.trb.2019.03.004.

Brevet,

Duhamel,

Iori and

Lacomme, A dial-a-ride problem using private vehicles and alternative nodes, Journal on Vehicle Routing Algorithms (2019), 89–107. doi:10.1007/s41604-019-00014-5.

A.M.

Campbell and

Savelsbergh, Efficient insertion heuristics for vehicle routing and scheduling problems, Transportation science38(3) (2004), 369–378. doi:10.1287/trsc.1030.0046.

Canadian Urban Transit Association, Specialized Transit Eligibility Certification Programs, Overview of Canadian and U.S. Experience, 2013. http://www.bv.transports.gouv.qc.ca/mono/1136638.pdf.

Cannon and

D.A.

Martin, Shaping National Disability Policy: Transportation Access and Social Security Reforms (2004), https://oac.cdlib.org/view?docId=hb2j49n5h3&query=&brand=oac4.

Chevaleyre,

P.E.

Dunne,

Endriss,

Lang,

Lemaître,

Maudet,

J.A.

Padget,

Phelps,

J.A.

Rodr and

Sousa, Issues in multiagent resource allocation, Informatica30 (2006), 37.

10.

Colorni and

Righini, Modeling and optimizing dynamic dial-a-ride problems, International transactions in operational research8(2) (2001), 155–166. doi:10.1111/1475-3995.00256.

11.

J.-F.

Cordeau and

Laporte, The dial-a-ride problem: Models and algorithms, Annals of Operations Research153(1) (2007), 29–46, http://link.springer.com/10.1007/s10479-007-0170-8 . doi:10.1007/s10479-007-0170-8.

12.

J.-F.

Cordeau,

Laporte,

J.-Y.

Potvin and

M.W.P.

Savelsbergh, Chapter 7 transportation on demand, in: Handbooks in Operations Research and Management Science,

Barnhart and

Laporte, eds, Transportation, Vol. 14, Elsevier, 2007, pp. 429–466, http://www.sciencedirect.com/science/article/pii/S0927050706140074 .

13.

J.-F.

Cordeau,

Laporte,

M.W.P.

Savelsbergh and

Vigo, Chapter 6 vehicle routing, in: Handbooks in Operations Research and Management Science, Vol. 14, Elsevier, 2007, pp. 367–428, https://linkinghub.elsevier.com/retrieve/pii/S0927050706140062 . ISBN 978-0-444-51346-5.

14.

Coslovich,

Pesenti and

Ukovich, A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem, European Journal of Operational Research175(3) (2006), 1605–1615. doi:10.1016/j.ejor.2005.02.038.

15.

Cramton,

Shoham and

Steinberg, An overview of combinatorial auctions, ACM SIGecom Exchanges7(1) (2007), 3–14, http://portal.acm.org/citation.cfm?doid=1345037.1345039 . doi:10.1145/1345037.1345039.

16.

Danassis,

Filos-Ratsikas and

Faltings, 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. 215–222, https://www.ijcai.org/proceedings/2019/31 . ISBN 978-0-9992411-4-1.

17.

K.C.

Dey,

Rayamajhi,

Chowdhury,

Bhavsar and

Martin, Vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communication in a heterogeneous wireless network – performance evaluation, Transportation Research Part C: Emerging Technologies68 (2016), 168–184, http://www.sciencedirect.com/science/article/pii/S0968090X16300018 . doi:10.1016/j.trc.2016.03.008.

18.

Egan and

Jakob, Market Mechanism Design for Profitable On-Demand Transport Services, 2015, arXiv:1501.01582 [cs].

19.

El Falou,

Itmi,

El Falou and

Cardon, On demand transport system’s approach as a multi-agent planning problem, in: 2014 International Conference on Advanced Logistics and Transport (ICALT), IEEE, 2014, pp. 53–58.

20.

Glaschenko,

Ivaschenko,

Rzevski and

Skobelev, Multi-agent real time scheduling system for taxi companies, in: AAMAS2009, p. 8.

21.

J.M.S.

Grau and

M.A.E.

Romeu, Agent based modelling for simulating taxi services, Procedia Computer Science52 (2015), 902–907, https://linkinghub.elsevier.com/retrieve/pii/S187705091500962X . doi:10.1016/j.procs.2015.05.162.

22.

J.M.S.

Grau,

M.A.E.

Romeu,

Mitsakis and

Stamos, Agent based modeling for simulation of taxi services, Journal of Traffic and Logistics Engineering1(2) (2013), 159–163. doi:10.12720/jtle.1.2.159-163.

23.

Gschwind and

Drexl, Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem, Transportation Science53(2) (2019), 480–491.

24.

C.H.

Häll,

Andersson,

J.T.

Lundgren and

Värbrand, The integrated dial-a-ride problem, Public Transport1(1) (2009), 39–54. doi:10.1007/s12469-008-0006-1.

25.

Helsgaun, General k-opt submoves for the Lin–Kernighan TSP heuristic, Mathematical Programming Computation1(2) (2009), 119–163. doi:10.1007/s12532-009-0004-6.

26.

J.J.

Jaw,

A.R.

Odoni,

H.N.

Psaraftis and

N.H.

Wilson, A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows, Transportation Research Part B: Methodological20(3) (1986), 243–257. doi:10.1016/0191-2615(86)90020-2.

27.

Krishna, Introduction, in: Auction Theory,

Krishna, ed., Academic Press, San Diego, 2003, pp. 1–10, http://www.sciencedirect.com/science/article/pii/B9780124262973500278 . ISBN 978-0-12-426297-3. doi:10.1016/B978-012426297-3.50027-8.

28.

Lehmann,

Müller and

Sandholm, The winner determination problem, in: Combinatorial Auctions,

Cramton,

Shoham and

Steinberg, eds, The MIT Press, 2005, pp. 297–318, http://mitpress.universitypressscholarship.com/view/10.7551/mitpress/9780262033428.001.0001/upso-9780262033428-chapter-13 . ISBN 978-0-262-03342-8. doi:10.7551/mitpress/9780262033428.003.0013.

29.

O.B.

Madsen,

H.F.

Ravn and

J.M.

Rygaard, A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives, Annals of Operations Research60(1) (1995), 193–208. doi:10.1007/BF02031946.

30.

Mingozzi,

Bianco and

Ricciardelli, Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints, Operations Research45(3) (1997), 365–377. doi:10.1287/opre.45.3.365.

31.

Muelas,

LaTorre and

J.-M.

Peña, A distributed VNS algorithm for optimizing dial-a-ride problems in large-scale scenarios, Transportation Research Part C: Emerging Technologies54 (2015), 110–130. doi:10.1016/j.trc.2015.02.024.

32.

S.N.

Parragh,

K.F.

Doerner and

R.F.

Hartl, Demand responsive transportation, Wiley Encyclopedia of Operations Research and Management Science (2010).

33.

Picard,

Balbo and

Boissier, Approches multiagents pour l’allocation de courses à une flotte de taxis autonomes, in: RIA2018, Revue D’intelligence Artificielle, 2018, pp. 223–247. doi:10.3166/RIA.32.223-247.

34.

Posada,

Andersson and

C.H.

Häll, The integrated dial-a-ride problem with timetabled fixed route service, Public Transport9(1–2) (2017), 217–241, http://link.springer.com/10.1007/s12469-016-0128-9.

35.

Ronald,

Thompson and

Winter, Simulating demand-responsive transportation: A review of agent-based approaches, Transport Reviews35(4) (2015), 404–421. doi:10.1080/01441647.2015.1017749.

36.

M.W.P.

Savelsbergh and

Sol, The general pickup and delivery problem, Transportation Science29(1) (1995), 17–29, http://pubsonline.informs.org/doi/abs/10.1287/trsc.29.1.17 . doi:10.1287/trsc.29.1.17.

37.

Schroten,

van Grinsven,

Tol,

Leestemaker,

P.-P.

Schackmann,

Vonk-Noordegraaf,

van Meijeren,

Kalisvaart, Research for TRAN Committee: The impact of emerging technologies on the transport system, Technical Report.

38.

Shen and

Lopes, Managing autonomous mobility on demand systems for better passenger experience, in: PRIMA 2015: Principles and Practice of Multi-Agent Systems, Vol. 9387, Springer, 2015, pp. 20–35, arXiv:1507.02563 [cs].

39.

Shoham, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2009, p. 532.

40.

M.M.

Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research35(2) (1987), 254–265, http://www.jstor.org/stable/170697 . doi:10.1287/opre.35.2.254.

41.

The Working Group for WLAN Standards, IEEE 802.11, The Working Group Setting the Standards for Wireless LANs, https://www.ieee802.org/11/.

42.

TRB’s Transit Cooperative Research Program (TCRP) Report 124, Guidebook for Measuring, Assessing, and Improving Performance of Demand-Response Transportation, Vol. 124, Transportation Research Board, Washington, DC, 2008.

43.

Vallee,

Oulamara and

W.R.

Cherif-Khettaf, New online reinsertion approaches for a dynamic dial-a-ride problem, Journal of Computational Science47 (2020). doi:10.1016/j.jocs.2020.101199.

44.

R.R.S.

van Lon,

Holvoet,

Vanden Berghe,

Wenseleers and

Branke, Evolutionary synthesis of multi-agent systems for dynamic dial-a-ride problems, in: Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference Companion – GECCO Companion’12, ACM Press, Philadelphia, Pennsylvania, USA, 2012, p. 331, http://dl.acm.org/citation.cfm?doid=2330784.2330832 . ISBN 978-1-4503-1178-6. doi:10.1145/2330784.2330832.

45.

Zargayouna,

Balbo and

Ndiaye, Generic model for resource allocation in transportation. Application to urban parking management, Transportation Research Part C: Emerging Technologies71 (2016), 538–554, http://www.sciencedirect.com/science/article/pii/S0968090X16301589 . doi:10.1016/j.trc.2016.09.002.