Funding source: Caltrans

Contract number: 65A0533

Funding amount: $100,000

Performance period: 3/2/2017 to 6/30/2018

Project description

The problem we study in this report focuses on routing in real time a fleet of capacitated vehicles to satisfy requests submitted by a set of customers while assigning the service cost fairly among the requested customers. During each operation, only a subset of the customers request service with some of them known at the beginning of the operation and the rest arriving dynamically during the day. The exact time points of these dynamic requests are unknown at the beginning of the day.

We propose a Hybrid Proportional Online Cost Sharing (HPOCS) mechanism to tackle the cost sharing problem and analyze its performance using simulation instances. Although HPOCS does satisfy the desirable properties, namely online fairness, budget balance, immediate response, individual rationality and ex-post incentive compatibility, it has certain drawbacks when the number of dynamic customers is small and does not give sufficient incentive for customers to request early. Therefore, we make two extensions to HPOCS: 1) we extend it to introduce the idea of discounts to encourage customers to submit their request in advance to better facilitate efficient vehicle routing; 2) we extend it to incorporate a dynamic vehicle routing framework that periodically re-optimizes the current vehicle routes. Both extensions include performance analysis and the tradeoff between the performance and the loss of certain desirable properties.

In general, our proposed mechanism, along with its extensions can generate efficient cost sharing solutions that satisfy desirable properties, reduce overall operating cost (mainly vehicle miles travelled) and provide sufficient incentives to customers to request service early in support of horizontal cooperation.