The Competitive Pickup and Delivery Orienteering Problem for Balancing Car-Sharing Systems

We present mixed-integer linear programming formulations for a pickup and delivery orienteering problem under different business models with multiple (competing) operators. Structural solution properties, including existence of equilibria and bounds on losses as a result of competition, of the competitive pickup and delivery problem under the restrictions of unit-demand stations, homogeneous payoffs, and indifferent customers based on results for congestion games are derived.

Two algorithms to find a Nash equilibrium for real-life instances are proposed. One can find equilibria in the most general case; the other can only be applied if the game can be represented as a congestion game, that is, under the restrictions of homogeneous payoffs, unit-demand stations, and indifferent customers.

In a numerical study, we compare different business models for car-sharing operations, including a merger between operators and outsourcing relocation operations to a common service provider (coopetition). Gross profit improvements achieved by explicitly incorporating competitor decisions are substantial, and the presence of competition decreases gross profits for all operators (compared with a merger).

Using a Munich, Germany, case study, we quantify the gross profit gains resulting from considering competition as approximately 35% (over assuming absence of competition) and 12% (over assuming that the competitor is omnipresence) and the losses because of the presence of competition to be approximately 10%. (joint work with Stefan Minner, Diogo Pocas, Andreas S. Schulz)

Lunch will be provided (vegetarian option included).