A scalable non-myopic dynamic dial-a-ride and pricing problem

• Dynamic dial-a-ride is studied as a solution for last mile problem and smart cities.
• Ignoring pricing leaves an incomplete and less efficient non-myopic DARP.
• Proposed a social optimal toll for queues under multi-server queue-based DARP.
• Results show improvement in social welfare over prior policies that ignored price.
• Guidelines for fleet design and shared-use policies under non-myopic pricing.

Non-myopic dial-a-ride problem and other related dynamic vehicle routing problems often ignore the need for non-myopic pricing under the assumption of elastic demand, which leads to an overestimation of the benefits in level of service and resulting inefficiencies. To correct this problem, a new dynamic dial-a-ride policy is introduced, one that features non-myopic pricing based on optimal tolling of queues to fit with the multi-server queueing approximation method proposed by Hyttiä et al. (2012) for large-scale systems. By including social optimal pricing, the social welfare of the resulting system outperforms the marginal pricing assumed for previous approaches over a range of test instances. In the examples tested, improvements in social welfare of the non-myopic pricing over the myopic pricing were in the 20–31% range. For a given demand function, we can derive the optimal fleet size to maximize social welfare. Sensitivity tests to the optimal price confirm that it leads to an optimal social welfare while the marginal pricing policy does not. A comparison of single passenger taxis to shared-taxis shows that system cost may reduce at the expense of decreased social welfare, which agrees with the results of Jung et al. (2013).