By Dr Michelle Dunbar
In many modern cities, transport infrastructure has typically developed according to a radial pattern, in response to urban-sprawl. However, as the population continues to grow and spread outwards from the CBD, existing transport infrastructure may be insufficient to cope with the increased travel demand. This may in turn lead to inaccessibility to public transport for commuters in these areas, resulting in increased car usage; exacerbating traffic congestion.
Figure 1: A Heat-map of Sydney’s Population density (source RP Data). Green lines (sketch) indicate the major rail infrastructure; Transport Interchanges (Hubs) are denoted by grey triangles.
Figure 2: An illustrative scenario depicting commuters without easy access to public transport, and labelled (by colour) according to their individual priority, and value-of-time.
With the boom in mobile technology and its app-services, demand-responsive transport has increased in popularity in the last few years as a means of complementing existing fixed services. Shuttle-bus services such as Melbourne’s SkyBus, allow commuters to connect with a number of different transport modes at the Transport Hub, Southern Cross station. Connections include: – Bus, Tram, Intercity and suburban trains and even direct connections with Tullamarine airport.
My current research involves developing an extension of the classical Vehicle Routing Problem with Time Windows (VRPTW) and the static Dial-a-Ride Problem (DARP). The research literature is rich with variations of these classical problems; however one of the major limitations is that they assume each passenger is identical with respect to value-of-time and focus only on the current routing, ignoring the multi-modal aspect of a passenger’s trip. The novel aspect of this research lies in the optimisation of passenger-centric measures in addition to those of benefit to the operator. These measures take into account the heterogeneity in each passenger’s value-of-time and the potential cost of missing their outbound mode at the Transport Hub – so as to design routes that minimise total travel time cost and missed connection cost.
The mathematical model developed to capture these aspects is formulated in C++ with optimal solutions obtained via the solver SCIP, for 40 randomly-generated datasets. Preliminary results indicate that the inclusion of passenger-centric measures has the potential to greatly improve customer perceptions of quality-of-service with only a minor increase to the travel time cost. See Figure 3 for an example of one such solution.
Figure 3: A comparison of the effectiveness of the new approach (time + missed connection) cost model (right) over the existing VRPTW approach (left). It may be observed that for the same number of vehicles, the cost of missed connections can be reduced to 0, for only one extra unit increase in travel-time cost. Red routes in the left figure denote routes containing at least one passenger who misses their connection at the Transport Hub.
The applications of this work also extend to the perishable-good delivery problem, in which items to be delivered are heterogeneous with respect to delivery priority and for which a penalty is incurred for late delivery. Future work will focus on developing and including additional passenger-centric measures as part of the optimisation and enhancing the robustness of this approach under operational uncertainty.