Time window based vehicle routing system
Mäntysaari, Juho (2017)
2017
Teknis-luonnontieteellinen
Teknisten tieteiden tiedekunta - Faculty of Engineering Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2017-09-06
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-201708241807
https://urn.fi/URN:NBN:fi:tty-201708241807
Tiivistelmä
Avoiding deadlocks and starvation is important for all vehicle systems, as both of them can cause a complete halt in traffic. Traditionally, deadlock and starvation issues are addressed with careful layout and traffic rule design. While this might prevent deadlocks and starvation events from halting the system, it causes severe performance decreasing limitations to possible layout solutions in addition of making system design difficult and expensive.
The time window based approached recommended in this thesis, provides an alternative solution for solving deadlock and starvation issues. It works by combining information on used pathways and their usage times in plans. By knowing when previously routed vehicles plan to use each layout element, the route search can produce plans that avoid deadlocks and starvation on any layout without predefined traffic rules. This allows several performance improving layout solutions like bidirectional lanes that a forbidden in traffic rule based systems.
This thesis first presents a new and effective time window based route search algorithm and then uses it to develop an effective and robust vehicle control system that can stand the inevitable deviations from planned element usage times. This addresses a major limitation with previous time window based proposals. It then demonstrates the effectiveness of the system against a more traditional traffic rule based system, by using both of them to run a simulated taxi system. Because the time window based solution allows better utilization of the available layout, it provides, depending on the number of vehicles, 10 to 33 % improvement over the traffic rule based approach.
The time window based approached recommended in this thesis, provides an alternative solution for solving deadlock and starvation issues. It works by combining information on used pathways and their usage times in plans. By knowing when previously routed vehicles plan to use each layout element, the route search can produce plans that avoid deadlocks and starvation on any layout without predefined traffic rules. This allows several performance improving layout solutions like bidirectional lanes that a forbidden in traffic rule based systems.
This thesis first presents a new and effective time window based route search algorithm and then uses it to develop an effective and robust vehicle control system that can stand the inevitable deviations from planned element usage times. This addresses a major limitation with previous time window based proposals. It then demonstrates the effectiveness of the system against a more traditional traffic rule based system, by using both of them to run a simulated taxi system. Because the time window based solution allows better utilization of the available layout, it provides, depending on the number of vehicles, 10 to 33 % improvement over the traffic rule based approach.