Non-myopic vehicle and route selection in dynamic DARP with travel time and workload objectives

https://doi.org/10.1016/j.cor.2012.03.002Get rights and content

Abstract

In dial-a-ride problems, a fleet of n vehicles is routed to transport people between pick-up and delivery locations. We consider an elementary version of the problem where trip requests arrive in time and require an immediate vehicle assignment (which triggers an appropriate route update of the selected vehicle). In this context, a relatively general objective can be stated as a weighted sum of the system's effort and the customers' inconvenience. However, optimizing almost any objective in this immensely complex stochastic system is prohibitively difficult. Thus the earlier work has largely resorted to heuristic cost functions that arise, e.g., from the corresponding static systems. By using the framework of Markov decision processes and the classical M/M/1 queue as a highly abstract model for a single vehicle, we explain why certain intuitive cost functions indeed give satisfactory results in the dynamic system, and also give an explicit interpretation of different components appearing in a general cost function. The resulting family of heuristic control policies is demonstrated to offer a desired type of performance thus justifying the assumed analogy between a multi-queue and dial-a-ride systems.

Introduction

Various vehicle routing problems have been studied actively since 1970s. The main focus has been on static or deterministic problems, where, e.g., a given set of objects need to be transported with a given vehicle(s). In dynamic vehicle routing problems, the situation is essentially different. Transport requests arrive in time according to some stochastic pattern, and the task is to route the vehicles in an online fashion to satisfy the demand.

A static dial-a-ride problem (DARP) is a vehicle routing problem with a focus on transporting people. Customers are known beforehand and each customer is associated with both a pick-up and a delivery location. Additionally, the pick-up and delivery times are often tightly constrained. In contrast, the dynamic dial-a-ride problem is a vehicle routing problem where the vehicles' routes are modified in real-time in response to trip requests arriving in time. Similarly as in the static case, the requests can also include some constraints, e.g., on the latest delivery time. For each request, a control policy assigns a vehicle, the route of which is modified accordingly. A response to a customer may include a time-window or an estimate for pick-up and delivery. Even with a fixed number of vehicles, control of such a system is a complex task where two conflicting objectives can be identified: (i) the system's effort, and (ii) the customers' interests. When the transport capacity is barely sufficient, the solutions to these two objectives converge to the only stable solution capable of serving the given travel demand. Otherwise, an appropriate balance between the chosen objectives must be sought. If longer travel times are tolerated, more trips can be combined and less kilometers are required to handle the demand. Conversely, customers requiring faster travel times imply a less efficient use of the transport capacity.

In this paper, we consider a variant of the dynamic dial-a-ride problem where trip requests are immediate and pick-up and delivery constraints are relaxed. A response to a customer fixes a vehicle and provides an initial pick-up and delivery time estimate for the trip. Customers (or items in a parcel service) are flexible in the sense that they tolerate (small) delays in their pick-up and delivery times. The flexibility allows accommodation of new trips to an existing route, which leads to an efficient real-time operation. Given that the system operates under a sufficiently dense demand, one obtains a low cost passenger transport system with small delays (cf., waiting time distributions in [25]). Customers can also be informed about delays in order to mitigate the adverse effects, e.g., by means of mobile communication to a smartphone. The results of this paper are general and apply also to, e.g., parcel service system, where substantially longer delays can be tolerated.

The system is controlled by two decisions for each trip request: vehicle assignment and route plan update. These actions, constitute the control policy that is a solution to our dynamic dial-a-ride problem. In the literature, policies ignoring the future requests are often referred to as the myopic policies. Our main contribution is to provide a solid motivation for a class of non-myopic policies that take into account the unknown future requests.

The enormous complexity of the system defies straightforward solutions and, therefore, we turn to an elementary stochastic system, a single server M/M/1 queue with known job sizes, in our search for analogous phenomena. By utilizing the framework of Markov decision processes, we derive exact results for the cost of accepting a given customer (certain workload) into a queue. The cost is expressed in terms of the additional delay passengers collectively experience or the additional amount of work the server conducts over an infinite time horizon. In a dispatching problem to multiple parallel queues with queue specific known service requirements, the obtained M/M/1 results can be applied to identify the best queue for each arriving customer. In contrast to the traditional dispatching problem, we consider server specific service requirements, i.e., a task takes a different effort from each server.

We use such a system to model the dynamic DARP and obtain cost functions, which define the vehicle selection and routing criterion. The cost function attempts to quantify the effect of vehicle and route selection in terms of the overall objective, thus allowing a comparison between alternative decisions. The server specific efforts in the abstract queueing model reflect the fact that in DARP vehicles are in different positions to accept each trip request. By numerical experiments, we show that the analogy is sufficiently strong so that the quantities that contribute to the cost in the M/M/1 case can be successfully utilized in vehicle selection and route update. Although the resulting policy has a close resemblance the previously used heuristics, the understanding gained from our approach sheds new light in solving dynamic DARPs in a scalable and non-myopic fashion.

Section snippets

Related work

The dynamic dial-a-ride problem has been widely studied in the past in different flavors, see [1] and [2] for extensive surveys of the field. Results from the corresponding static problems, cf. e.g., [3], [4], have given rise to solution methods that either consider the dynamic system in static batches or directly apply the static solutions as approximations for the dynamic case. In [5], a dynamic programming solution to a single vehicle problem with immediate requests is presented under

Preliminaries

Next we first briefly define the model and notation of the dynamic dial-a-ride problem. The resulting stochastic optimization problem is then elaborated into a form that allows considering the problem in the MDP context.

Multi-queue model for the dynamic DARP

As mentioned, the complete stochastic model describing a dynamic DARP is prohibitively complex, and thus we approach the problem by modeling each vehicle as a simple queue in a multi-queue system. Although the two models seem quite different at first glance, some fundamental properties are similar. These allow assessing the effects of the decisions on the future requests and, indeed, turn out to be beneficial in defining a parameterized control policy for the dynamic DARP.

In particular, we

M/M/1 inspired control policy for dial-a-ride system

In the previous section, we derived closed form expressions (6), (9) for the relative values with respect to the mean sojourn time and the server's load in an M/M/1 queue, in which the service times become known upon arrival. These results were then utilized to derive an efficient dispatching policy in the setting of parallel queues with queue specific service requirements.

Inspired by this, we propose a parameterized heuristic control policy for vehicle and route selection in a dial-a-ride

Conclusions

The dynamic dial-a-ride problem is a very difficult stochastic control problem. To the best of our knowledge, this is the first paper to provide a sound theoretic approach to develop a non-myopic family of control policies for the dynamic DARP. The derived policies turn out to be similar to some frequently used intuitive heuristic policies. The considered control policies are also computationally lightweight and robust, and thus suitable for large-scale dial-a-ride systems consisting of

Acknowledgments

This work was supported by the Finnish Funding Agency for Technology and Innovation, Finnish Ministry of Transport and Communications, Helsinki Metropolitan Area Council and Helsinki City Transport. The authors would also like to thank Prof. Samuli Aalto for his invaluable comments during the preparation of this article.

References (30)

  • C.E. Cortés et al.

    Hybrid adaptive predictive control for a dynamic pickup and delivery problem

    Transportation Science

    (2009)
  • W. Powell

    A comparative review of alternative algorithms for the dynamic vehicle allocation problem

  • R. Bent et al.

    Scenario-based planning for partially dynamic vehicle routing with stochastic customers

    Operations Research

    (2004)
  • Virtamo J, Aalto S. Procedure for controlling an elevator group. US patent 5,503,249;...
  • Hyytiä E, Virtamo J. Dynamic routing and wavelength assignment using first policy iteration. In: The fifth IEEE...
  • Cited by (47)

    • Dynamic vehicle routing with random requests: A literature review

      2023, International Journal of Production Economics
      Citation Excerpt :

      Besides, 33% of DPDP instances are arbitrarily generated or derived from the static P&D problem instances of Li and Lim (2001) and Ropke et al. (2007). Sheridan et al. (2013) generate their instances using the Automod software, while the other authors reuse the existing DPDP instances created by Caramia et al. (2002), Pankratz (2005), Hyytiä et al. (2012), and van Lon et al. (2016). The solution approaches developed for DPDPs are summarized in Table 7.

    • Comparison of anticipatory algorithms for a dial-a-ride problem

      2022, European Journal of Operational Research
    • Choice-driven dial-a-ride problem for demand responsive mobility service

      2022, Transportation Research Part B: Methodological
    • The pickup and delivery problem with synchronized en-route transfers for microtransit planning

      2022, Transportation Research Part E: Logistics and Transportation Review
    • Matching and routing for shared autonomous vehicles in congestible network

      2021, Transportation Research Part E: Logistics and Transportation Review
    • Simulation-based design and analysis of on-demand mobility services

      2021, Transportation Research Part A: Policy and Practice
      Citation Excerpt :

      In the extreme, prebooking all rides before operations results in the static DARP which provides a lower bound to the KPIs. The FRD differs from the analysis in Hyytiä et al. (2012) in several major ways. First, its shape is not the product of modifying the weights in the objective function but of changing the guaranteed service level.

    View all citing articles on Scopus
    View full text