Browsing by Subject "Dispatching"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item A Fast, Auction-Based Algorithm for Paratransit Vehicle Assignment(Center for Transportation Studies, University of Minnesota, 2013-09) Carlsson, John Gunnar; Houle, JasonA problem based on the actual passenger transportation operations of two community disability service organizations in St. Paul is presented. The problem is to minimize the number of routes needed to serve all the passengers subject to spatial and temporal constraints on the routing of vehicles. Additional problem characteristics include heterogeneous vehicle and passenger classes, multiple destinations, separate "runs" defined by service time windows, and rules governing the embarkment as well as maximum travel times. Here we develop a method able to generate a good problem solution within a reasonable amount of time to guide these companies' operations. Early attempts at problem solution reveal facets of its structure and illuminate an inherent trade-off between vehicle capacity and uninhibited vehicle operating time. To address this, the method proposed uses high-capacity vehicles to serve routes in both runs while allotting easily served passengers to these vehicles to relieve temporal constraints. This heuristic carries the additional advantage of partitioning the rest of the solution into two single-run problems, and the decrementing adaptive memory program (DAMP) is devised as a way of discovering solution components and promoting those more effective at producing good solutions to be used in future attempts. When applied to a data set provided by the organizations, the algorithm improved the current benchmark solution, generated by hand, by over 12% in reasonable operating time, serving 574 passengers with 64 routes in 53 vehicles. Its absolute measure of quality, in light of lower bounds that were constructed, is also considered good.Item Pressure-based dispatch for shared autonomous vehicles(Center for Transportation Studies, University of Minnesota, 2019-08) Levin, Michael; Kang, DiShared autonomous vehicle (SAV) technology is rapidly maturing, with two companies (Uber and Waymo) already testing SAV services in cities in the US. Due to the point-to-point service and lack of a driver, SAV service costs could be similar to that of personal vehicles, resulting in major mode choice changes for daily travel. A major issue for SAV operators is the SAV dispatch problem, i.e., how to optimally assign vehicles to waiting passengers. SAV dispatch is essentially a vehicle routing problem, which is NP-hard, and is complicated by fleets measured in thousands of vehicles in typical cities. Previous studies have attempted to quantify the number of passengers served per SAV using agent-based simulation studies on realistic networks, with a variety of results that highly depend on the heuristic chosen for SAV dispatch. Ideally, the optimal SAV dispatch strategy would serve as many passengers as any other policy. This project created a max-pressure dispatch policy, which was analytically proven by showing stability in the number of unserved passengers through a Lyapunov function. Essentially, the work analytically compared the serviceable demand from the max-pressure dispatch to the demand that could be served by any other dispatch policy. The max-pressure policy relied on a planning horizon; as the horizon grows to infinity, the policy becomes arbitrarily close to any sequence of SAV movements that can serve given demand rates.