# The Importance of Modeling Path Choice Behavior in the Vehicle Routing Problem
## 1 Introduction
The PCP output is the choice probability or rate for each path of the choice set of alternatives with deterministic or nondeterministic utility models (more details are reported in Section 3). 2. The VRP has the main objective of finding the best set of vehicles, routes and paths to follow in the context of transport problems (e.g., freight distribution, dial and ride for passengers, etc.). The problem specified for different transport modes, i.e., cars, buses and trucks [7], freight [8; 9], dial and ride [10; 11; 12], and it is solved with exact or heuristic procedures [13]. Exact solutions can be applied for a small system in acceptable  
Figure 1: State of the art’s classification. processing time and are based on Lagrangian relaxations or on the Dantzig-Wolfe decomposition. Some papers related to Lagrangian relaxations proposed adopting a branch-and-bound technique [14] or a branch algorithm [15]. Some papers related to the Dantzig-Wolfe decomposition proposed semisoft time windows [16] or rigid time windows [17]. The heuristic solution can be applied for real-size transport systems for the VRP solution in acceptable processing time and in most cases are based on natural metaheuristics procedures. Some papers related to the use of heuristic algorithms proposed adopting a parallel genetic approach [18; 19], a tabu search algorithm [20], simulated annealing [21], quantum annealing [22], an ant colony [23], a local search [24], a swarm optimization [25]. Given two consecutive nodes in the route, the PCP cannot be considered: with fixed and predefined static cost; without congestion with specific reference to the urban area; with a deterministic and monocriterion choice (e.g., travel time). A fixed travel cost for a path in an uncongested transport system, sometimes assumed in the VRP, is equivalent to studying the PCP and the VRP separately. This paper tries to bridge the gap between the PCP and the VRP. In this paper, the importance of modelling path choice behavior in the vehicle routing problem is investigated: the routing problem must be modeled considering the path choice with probabilistic models in a congested time-dependent system with pretrip and en route choices. Considering the objective of the paper, in Section 2, a general approach relating to the transport system analysis and some indications on the specific method proposed in this paper are introduced. Section 3 reports the PCP between two nodes; considering the objective of this paper, in Section 3, a comparison of the path choice models is reported in the consolidated area of the random utility approach. Section 4 reports path choice models in the context of the VRP and some numerical comparisons in a test system. Both Sections 3 and 4 contain definition and notation, models and discussions subsections. Section 5 reports some conclusions and further developments. The main contributions of this paper are:  
* The path choice models adopted to simulate a real choice are discussed from the analyst's point of view (Section 3);
* The effect of the path choice is considered in the more general VRP (Section 4).