Random utility models are the most widely used models for analysing and predicting route choice behaviour. In this context, a choice set for each origin-destination pair needs to be defined. The number of elementary pathsconnecting an origin to its destination can be very large. Assuming that a traveller chooses between all feasible paths is therefore not only behaviourally unrealistic, but can also cause operational problems in estimating and applying a route choice model. This motivates the need for using path enumeration algorithms for defining choice sets of limited size. Ideally, the choice set should contain all paths that a traveller might consider but no unreasonable paths. Moreover, only paths that are perceived as different by the travellers should be included. Indeed, in an urban network paths can have such a high degree of overlap that they may not be perceived as different by the travellers. A random sampling approach is proposed fordefining choice sets. It is motivated by the fact that Multinomial Logit and GEV models can be consistently estimated with a subset of randomly selected alternatives. In addition to a description of the proposed approach,a systematic comparison of existing path enumeration algorithms is provided on different networks. Performance measures that are dependent and independent of the observed path choices were developed. The approach proposedhere is based on subpaths where a subpath is a sequence of links. The originality of this approach is that the inclusion of a subpath in a choice set is modelled in a stochastic way based on the distance to the shortest path. More precisely, the probability associated with a subpath is defined by the double bounded Kumaraswamy distribution and the probabilities assigned to the subpaths can be controlled by the definition of the distribution parameters. This is a very flexible approach that can be used in variouspath enumeration algorithms (including those described in the literature). Two new approaches are proposed, a biased random walk algorithm and a forced passage algorithm. Each of these approaches has advantages and drawbacks. The final algorithm which is currently under development will combineboth approaches. The algorithms have been implemented in BioRoute which is a route choice modelling tool for BIOGEME. They have up to date been tested on a simplified Swiss network containing 39411 links and 14841 nodes. This is to our knowledge the largest network used for testing choice set generation algorithms. The results are very promising for both the biased random walk and the forced passage approaches. For the Swiss dataset, 50% of the observations were found by the link-elimination algorithm, while approximately 80% were found by using the algorithms. For the covering abstract see ITRD E137145.
Abstract