An Asymptotic, Probabilistic Analysis of a Routing Problem
David M. Stein
Source abstract
Certain “Bus Problems” are defined as generalizations of the traveling salesman problem. The simplest result concerns the length of the tour required by a single bus to pick up and deliver n passengers from random locations to random destinations in a bounded region of the plane. It is shown that the length of the tour divided by the square root of n converges almost surely to the square root of slightly more than twice the area of the region as n goes to infinity. When several buses are available, the length of the tour is simply divided by the number of buses. The bus problems have been motivated by the practical problem of scheduling dial-a-ride transportation systems.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.