Context and Objective

''The dial-a-ride problem (DARP) generalizes a number of well studied vehicle routing problems such as the Vehicle Routing Problem with Time Windows (VRPTW) in Toth and Vigo (2001) and the Pickup and Delivery Problem (PDP) in Parragh et al (2008). The DARP is a demand responsive transportation service, which arises for example in the context of patient transportation'' [Ritzinger et al. 2016]

The objective of this project is the definition and study of a distributed strategy for the management of a vehicle fleet ensuring an online dial-a-ride service.

  • This is a dynamic resource allocation problem of traveler requests (resources) to vehicles (consumers) (see figure).

  • Your strategy to solve this problem is performed by agents, i.e. the vehicles, which have to process at least 90% of traveler requests.

  • Agents are mobile, distributed and communicate with a global network.

  • By hypothesis, requests are emitted online non-deterministically by N specific nodes (S1, S2, S3 on figure) that are called sources.

  • A request (R1, . . . , R6 on figure) is defined by the following information:

    • two sources, i.e. the origin and the destination of the travel,

    • a temporal window, i.e. when the request has to be satisfied,

    • optional properties like the number of passengers, the need of baby seats.

  • Vehicles (V1, . . . , V6 on figure) are mobile, distributed and communicate through a global network (figure).

  • By hypothesis, vehicles belong to the same fleet and are cooperative. It implies that they share information and are not voluntarily competitive in satisfying requests.

    In the example, red vehicles are riding passengers and dark vehicles are free. Vehicles have to process at least 90% of traveler requests.

dap
Figure 1. Vehicle fleet management example

Work to realise

Based on the above problem description, each group proposes one strategy to solve this allocation problem.

The assessment of the strategy will be done with the multi-agent simulation platform netLogo or Repast.

For simplification purpose:

  • Vehicles move in an Euclidian space.

  • Sources emit their request until a vehicle rides the client or the maximum value of the temporal window request is overpassed.

  • All messages are received by all vehicles

  • Requests are related to one client

  • Vehicle cannot satisfy simultaneously several requests (i.e. several client like in carpooling)

References

[Ritzinger et al. 2016]

Ritzinger, U., Puchinger, J., & Hartl, R. F. (2016). Dynamic programming based metaheuristics for the dial-a-ride problem. Annals of Operations Research, 236(2), 341-358.