Urban Freight Transportation Planning: A Dynamic Stackelberg Game-Theoretic Approach

Bo Zhang, Tao Yao, Terry L. Friesz, Hongcheng LiuarXiv 2012 · DOI · arXiv

Abstract

In this paper, we propose a dynamic Stackelberg game-theoretic model for urban freight transportation planning designed to characterize the complex interactions between freight and personal transportation. The problem is formulated as a bi-level dynamic mathematical program with equilibrium constraints (MPEC). The upper level represents a truck company seeking a system optimum (SO) to minimize total costs, while the lower level characterizes the dynamic user equilibrium (DUE) of inhomogeneous traffic. We derive a mathematical program with complementarity constraints (MPCC) reformulation and utilize a projected gradient algorithm to solve this computationally intensive problem. Numerical experiments demonstrate that background traffic is non-negligible in freight planning, even when truck volumes are relatively small. Furthermore, our model identifies a dynamic instance of a Braess-like Paradox, offering managerial insights for metropolitan planning organizations (MPOs) to increase social welfare by strategically restricting freight movement.

Introduction: The Conflict of Urban Mobility

Urban freight planning, often categorized under "city logistics," has traditionally focused on the Vehicle Routing Problem (VRP)—the optimization of delivery paths and schedules to minimize operational costs. However, these traditional models frequently treat the surrounding city traffic as a static background. In reality, urban roads are a shared resource where trucks and private vehicles compete for limited capacity.

When a freight company alters its scheduling or routing, it changes the congestion profile of the network. Private commuters, acting in their own self-interest, respond by shifting their departure times or routes. This reactive behavior creates a feedback loop that ultimately affects the freight company's own efficiency. This research addresses this gap by modeling the timely, strategic interactions between freight leaders and commuter followers.

A Bi-Level Game-Theoretic Framework

The researchers formulate this interaction as a Dynamic Stackelberg Game, structured as a bi-level Mathematical Program with Equilibrium Constraints (MPEC):

  • The Upper Level (The Leader): A truck company aiming for a System Optimum (SO). The objective is to minimize total transportation costs, including travel time and operational expenses, while satisfying all delivery demands.
  • The Lower Level (The Followers): Individual private vehicle drivers who reach a Dynamic User Equilibrium (DUE). These drivers selfishly choose routes and departure times to minimize their individual travel costs and penalties associated with arriving too early or too late at their destinations.

This framework acknowledges that the truck company has the "first-move" advantage in planning, but must account for the inevitable equilibrium shift of the commuting public.

Computational Strategy: From MPEC to MPCC

Solving bi-level dynamic programs is notoriously difficult due to their non-convex and non-differentiable nature. To make the model computationally tractable, the authors employed several key strategies:

  1. MPCC Reformulation: The bi-level MPEC was transformed into a single-level Mathematical Program with Complementarity Constraints (MPCC) using penalty functions. This allows for the application of standard optimization techniques.
  2. Inhomogeneous Traffic Modeling: The model incorporates a link delay function where trucks and cars are treated differently. Specifically, a congestion factor ($\beta$) is used to represent the larger physical and operational footprint of trucks compared to private cars.
  3. Projected Gradient Algorithm: A specialized algorithm was developed to navigate the resulting non-convex optimization landscape and find local optima.

Experimental Insights: The Nguyen-Dupuis Network

The model was validated using the Nguyen-Dupuis network, a standard benchmark in transportation research featuring 19 nodes and 25 links. The study compared scenarios with varying freight demands (up to 5,000 trucks) against a baseline of 15,000 private vehicles.

The Importance of Background Traffic

A primary finding is that background traffic is "non-negligible." Even when trucks constitute a small percentage of the total vehicle count, their impact on congestion—and the subsequent reaction from commuters—is profound. The study found that when the truck company actively accounted for commuter reactions, they achieved total cost reductions ranging from 12.12% to 44.90% compared to models that ignored these dynamics.

The Dynamic Braess-like Paradox

Perhaps the most striking result is the discovery of a dynamic case of the Braess-like Paradox. In classical traffic theory, the Braess Paradox occurs when adding a road to a network actually slows down total travel time. In this dynamic freight context, the researchers found that restricting trucks from a specific arc (Arc 12 in the test network) improved the total social cost of the system by 1.6%.

While this restriction increased the truck company's specific costs by 11.1%, the resulting shift in commuter behavior led to a net gain for the city's overall traffic efficiency. This suggests that Metropolitan Planning Organizations (MPOs) could potentially increase social welfare by implementing freight-restricted zones or time-of-day restrictions, provided there are mechanisms to compensate freight operators for their increased costs.

Limitations and Future Directions

While the model provides a robust framework for integrated urban planning, several challenges remain:

  • Global Optimality: Due to the non-convexity of the problem, the current algorithm guarantees only local optima. Further research is needed to find more globally robust solutions.
  • Theoretical Proofs: Rigorous mathematical proofs for the existence of solutions in these specific dynamic MPEC models are still a work in progress.
  • Real-world Scaling: Future iterations should incorporate stochastic elements like uncertain travel demand, model competition between multiple truck companies (moving from MPEC to EPEC), and integrate public transit systems to provide a truly holistic view of urban mobility.

Summary updated

Abstract

In this paper we propose a dynamic Stackelberg game-theoretic model for urban freight transportation planning which is able to characterize the interaction between freight and personal transportation in an urban area. The problem is formulated as a bi-level dynamic mathematical program with equilibrium constraints (MPEC) which belongs to a class of computationally challenging problems. The lower level is dynamic user equilibrium (DUE) with inhomogeneous traffic that characterizes traffic system optimum (SO) freight transportation planning problem which aims at minimizing the total cost to a truck company. A mathematical program with complementarity constraints (MPCC) reformulation is derived and a projected gradient algorithm is designed to solve this computationally challenging problem. Numerical experiments are conducted to show that when planning freight transportation the background traffic is nonnegligible, even though the amount of trucks compared to other vehicles traveling on the same network is relatively small. What's more, in our proposed bi-level model for urban freight transportation planning, we find a dynamic case of a Braess-like Paradox which can provide managerial insights to a metropolitan planning organization (MPO) in increasing social welfare by restricting freight movement.
BibTeX
@misc{zhang2012urban,
  author = {Bo Zhang and Tao Yao and Terry L. Friesz and Hongcheng Liu},
  title = {{Urban Freight Transportation Planning: A Dynamic Stackelberg Game-Theoretic Approach}},
  year = {2012},
  eprint = {1211.3950},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1211.3950},
}
Figure