The combined distribution and stochastic assignment problem

Jan T. Lundgren 

Division of Optimization 
Department of Mathematics 
Linköping Institute of Technology
S-581 83 Linköping 
Sweden

and

Michael Patriksson

Department of Mathematics
Chalmers University of Technology
S-412 96 Gothenburg              
SWEDEN


ABSTRACT:

The combined distribution and assignment problem is the problem of the
simultaneous determination of the distribution of trips between origins and
destinations in a transportation network and the assignment of trips to routes in each origin--destination pair.  In the most widely used model the 
distribution is assumed to follow a gravity model with negative exponential
deterrence function and the assignment is made according to the
deterministic user equilibrium principle. In this paper we describe an
extension of this model in which the allocation of trips to routes is made
according to the principle of stochastic user equilibrium.
  
We discuss the behavioural foundations of trip assignment and combined
models assuming deterministic or stochastic route choice.  In particular, we
describe how they can be derived using the efficiency principle from
discrete choice theory; the combined distribution and stochastic assignment
model can be obtained as the continuous approximation of the discrete
problem of finding the most probable flow pattern under the assumption of
efficient trip making behaviour.
  
We outline an algorithm for the solution of the model which is based on a
route (column) generation algorithm, disaggregated simplicial decomposition,
and a partial linearization algorithm.  
  
KEY WORDS: Combined Transportation Planning Models, Stochastic User
Equilibrium, Efficiency Principle, Column Generation Algorithms, Partial
Linearization