Research Projects

Stop the Video

Research Projects

STATUS: Complete YEAR: 2016 TOPIC AREA: Integrating freight and passenger systems CENTER: METRANS UTC

An Online Cost Allocation Model for Horizontal Supply Chains

Project Summary

Project number: MT-16-02

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.


John Carlsson
Assistant Professor, Department of Industrial and Systems Engineering; Daniel J. Epstein Department of Industrial and Systems Engineering
3650 McClintock Ave.
Olin Hall of Engineering (OHE) 310FLos Angeles, CA 90089-0193
United States
[email protected]


Maged Dessouky
Dean's Professor and Chair, Daniel J. Epstein Department of Industrial and Systems Engineering
3715 McClintock Ave.
Ethel Percy Andrus Gerontology Center (GER) 206ALos Angeles, CA 90089-0193
United States
[email protected]