A combinatorial dynamic network trajectory reservation algorithm for connected autonomous vehicles.

*(English)*Zbl 07257993Summary: We present a combinatorial assignment algorithm for reserving space-time trajectories from origins to destinations given an ordered list of vehicles. Space-time trajectories include guaranteed arrival times at every node in the path, including at the destination. Traffic flows are modeled using the cell transmission model, a Godunov approximation to the kinematic wave model. Space-time trajectories are constructed to follow the cell transmission model constraints and first-in-first-out behavior. Reservation-based intersection control for connected autonomous vehicles, which determines intersection access and delays for individual vehicles, is used to ensure that reserved trajectories are followed. The algorithm is suitable for city networks. Results show that vehicles with higher priority tend to have much lower travel times. In addition, the trajectory reservation system reduced overall congestion in the network compared with dynamic user equilibrium assignments.

##### Keywords:

autonomous vehicles; trajectory reservation; dynamic traffic assignment; cell transmission model
Full Text:
DOI

##### References:

[1] | Akahane H, Kuwahara M (1996) A basic study on trip reservation systems for recreational trips on motorways. In: Proceedings of the 3rd world congress on intelligent transportation systems, pp 1-7 |

[2] | Akamatsu T, Wada K (2017) Tradable network permits: a new scheme for the most efficient use of network capacity. Transportation Research Part C: Emerging Technologies 79:178-195 |

[3] | Akamatsu T, Sato S, Nguyen L (2006) Tradable time-of-day bottleneck permits for morning commuters. JSCE Journal of Infrastructure Planning and Management 62(4):605-620 |

[4] | Carey M, Balijepalli C, Watling D (2015) Extending the cell transmission model to multiple lanes and lane-changing. Networks and Spatial Economics 15 (3):507-535 · Zbl 1338.90101 |

[5] | Carlino D, Depinet M, Khandelwal P, Stone P (2012) Approximately orchestrated routing and transportation analyzer: large-scale traffic simulation for autonomous vehicles. In: 2012 15th international IEEE conference on intelligent transportation systems (ITSC). IEEE, pp 334-339 |

[6] | Carlino D, Boyles SD, Stone P (2013) Auction-based autonomous intersection management. In: 2013 16th international IEEE conference on intelligent transportation systems-(ITSC). IEEE, pp 529-534 |

[7] | Chiu Y-C., Bottom J, Mahut M, Paz A, Balakrishna R, Waller T, Hicks J (2011) Dynamic traffic assignment: a primer. Transportation Research E-Circular (E-C153). https://trid.trb.org/view/1112932 |

[8] | Courant R, Friedrichs K, Lewy H (1967) On the partial difference equations of mathematical physics. IBM J Res Dev 11(2):215-234 · Zbl 0145.40402 |

[9] | Daganzo CF (1994) The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory. Transp Res B Methodol 28 (4):269-287 |

[10] | Daganzo CF (1995) The cell transmission model, part II: network traffic. Transp Res B Methodol 29(2):79-93 |

[11] | Dresner K, Stone P (2004) Multiagent traffic management: a reservation-based intersection control mechanism. In: Proceedings of the third international joint conference on autonomous agents and multiagent systems, vol 2. IEEE Computer Society, pp 530-537 |

[12] | Dresner K, Stone P (2006) Traffic intersections of the future. In: Proceedings of the national conference on artificial intelligence. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press, vol 21, no. 2, p 1593 |

[13] | Duell M, Levin MW, Boyles SD, Waller ST (2016) Impact of autonomous vehicles on traffic management: Case of dynamic lane reversal. Transportation Research Record: Journal of the Transportation Research Board (2567):87-94 |

[14] | Edara P, Teodorović D (2008) Model of an advance-booking system for highway trips. Transportation Research Part C: Emerging Technologies 16(1):36-53 |

[15] | Fredman ML, Tarjan RE (1987) Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM) 34(3):596-615 |

[16] | Godunov SK (1959) A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics. Matematicheskii Sbornik 89(3):271-306 · Zbl 0171.46204 |

[17] | Hausknecht M, Au T-C, Stone P (2011) Autonomous intersection management: multi-intersection optimization. In: 2011 IEEE/RSJ international conference on intelligent robots and systems (IROS). IEEE, pp 4581-4586 |

[18] | Heydecker B, Addison J (1996) An exact expression of dynamic traffic equilibrium. Transportation and traffic theory, pp 359-383 |

[19] | Kuwahara M, Akamatsu T (1993) Dynamic equilibrium assignment with queues for a one-to-many od pattern. Transportation and Traffic Theory 12:185-204 |

[20] | Le Vine S, Polak J (2016) A novel peer-to-peer congestion pricing marketplace enabled by vehicle-automation. Transp Res A Policy Pract 94:483-494 |

[21] | Levin MW (2017) Congestion-aware system optimal route choice for shared autonomous vehicles. Transportation Research Part C: Emerging Technologies 82:229-247 |

[22] | Levin MW, Boyles SD (2015) Intersection auctions and reservation-based control in dynamic traffic assignment. Transportation Research Record: Journal of the Transportation Research Board, (2497):35-44 |

[23] | Levin MW, Rey D (2017) Conflict-point formulation of intersection control for autonomous vehicles. Transportation Research Part C: Emerging Technologies 85:528-547 |

[24] | Levin MW, Pool M, Owens T, Juri NR, Waller ST (2014) Improving the convergence of simulation-based dynamic traffic assignment methodologies. Networks and Spatial Economics, pp 1-22 |

[25] | Levin MW, Boyles SD, Patel R (2016) Paradoxes of reservation-based intersection controls in traffic networks. Transp Res A Policy Pract 90:14-25 |

[26] | Levin MW, Fritz H, Boyles SD (2017) On optimizing reservation-based intersection controls. IEEE Trans Intell Transp Syst 18(3):505-515 |

[27] | Lighthill MJ, Whitham GB (1955) On kinematic waves. ii. a theory of traffic flow on long crowded roads. In: Proceedings of the royal society of london a mathematical, physical and engineering sciences, vol 229. The Royal Society, pp 317-345 · Zbl 0064.20906 |

[28] | Liu W, Yang H, Yin Y (2015) Efficiency of a highway use reservation system for morning commute. Transportation Research Part C: Emerging Technologies 56:293-308 |

[29] | Łukasiewicz P, Karpio K, Orłowski A (2012) The models of personal incomes in USA. Acta Phisica Polonica A 121:82-85 |

[30] | Nie M (2012) Transaction costs and tradable mobility credits. Transp Res B Methodol 46(1):189-203 |

[31] | Richards PI (1956) Shock waves on the highway. Oper Res 4(1):42-51 · Zbl 1414.90094 |

[32] | Schepperle H, Böhm K (2007) Agent-based traffic control using auctions. In: Cooperative information agents XI. Springer, pp 119-133 |

[33] | Schepperle H, Böhm K (2008) Auction-based traffic management: towards effective concurrent utilization of road intersections. In: 2008 10th IEEE Conference on E-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, E-Commerce and E-Services. IEEE, pp 105-112 |

[34] | Solé-Ribalta A, Gómez S, Arenas A (2018) Decongestion of urban areas with hotspot pricing. Networks and Spatial Economics 18(1):33-50 |

[35] | Su P, Park B (2015) Auction-based highway reservation system an agent-based simulation study. Transportation Research Part C: Emerging Technologies 60:211-226 |

[36] | Vasirani M, Ossowski S (2012) A market-inspired approach for intersection management in urban road traffic networks. J Artif Intell Res 43:621-659 · Zbl 1237.90058 |

[37] | Verhoef E, Nijkamp P, Rietveld P (1997) Tradeable permits: their potential in the regulation of road transport externalities. Environ Plann B Plann Des 24 (4):527-548 |

[38] | Vickrey WS (1969) Congestion theory and transport investment. Am Econ Rev 59(2):251-260 |

[39] | Wada K, Akamatsu T (2013) A hybrid implementation mechanism of tradable network permits system which obviates path enumeration: an auction mechanism with day-to-day capacity control. Procedia Soc Behav Sci 80:304-326 |

[40] | Waller ST, Ziliaskopoulos AK (2006) A combinatorial user optimal dynamic traffic assignment algorithm. Ann Oper Res 144(1):249-261 · Zbl 1156.90324 |

[41] | Wong J-T (1997) Basic concepts for a system for advance booking for highway use. Transp Policy 4(2):109-114 |

[42] | Yang H, Wang X (2011) Managing network mobility with tradable credits. Transp Res B Methodol 45(3):580-594 |

[43] | Ziliaskopoulos AK (2000) A linear programming model for the single destination system optimum dynamic traffic assignment problem. Transp Sci 34(1):37-49 · Zbl 1002.90013 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.