An Algorithm for the Combined Distribution and Assignment Problem

Jan Lundgren and Michael Patriksson
Department of Mathematics
Linköping Institute of Technology
S-581 83 Linköping
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.
We consider a model for such a problem where the distribution follows 
a gravity model and the assignment a user equilibrium model. The most 
well-known algorithm for this model is that of Evans (1976). 
Although this algorithm has been shown to be efficient compared to
algorithms such as the Frank--Wolfe method, which it generalizes, 
it builds the sequence of link flow solutions based on the same algorithmic
principle, and therefore also is subject to slow convergence.
We propose to combine Evans' approach with the disaggregate simplicial
decomposition (DSD) algorithm for updating the link flows; this leads
to a faster convergence, as well as other improvements.  For example, the
algorithm is less sensitive to inexact solutions of the entropy maximization
subproblems; it further provides explicit route flows in each of the  
origin--destination pairs.  Numerical results are presented for four small and
medium scale networks.