Search

The mean-standard deviation shortest path problem (MSDSPP) incorporates the travel time variability into the routing optimization. The idea is that the decision-maker wants to minimize the travel time not only on average, but also to keep their variability as small as possible. Its objective is a linear combination of mean and standard deviation of travel times. This study focuses on the problem of finding the best- K optimal paths for the MSDSPP. We denote this problem as the KMSDSPP. When the travel time variability is neglected, the KMSDSPP reduces to a K -shortest path problem with expected routing costs. This paper develops two methods to solve the KMSDSPP, including a basic method and a deviation path-based method. To find the k + 1 th optimal path, the basic method adds k constraints to exclude the first- k optimal paths. Additionally, we introduce the deviation path concept and propose a deviation path-based method. To find the k + 1 th optimal path, the solution space that contains the k th optimal path is decomposed into several subspaces. We just need to search these subspaces to generate additional candidate paths and find the k + 1 th optimal path in the set of candidate paths. Numerical experiments are implemented in several transportation networks, showing that the deviation path-based method has superior performance than the basic method, especially for a large value of K . Compared with the basic method, the deviation path-based method can save 90.1% CPU running time to find the best 1000 optimal paths in the Anaheim network. [ABSTRACT FROM AUTHOR]

Travel times in real-world transportation networks are affected by many disruptions. When we conduct the network design optimization, the traffic condition and its resulting travel time variability should be taken into account. However, most of the previous network design optimizations adopted the lengths or expected travel times of links. Based on travel time means and standard deviations, we develop an arc-based model that is a nonlinear and concave integer program. By the Dantzig-Wolfe reformulation, we transform it into an equivalent column-based model that is an integer linear program with a large number of variables. Based on the column-based model, we develop a hybrid method based on column generation and Lagrangian relaxation. The restricted master problem can be settled by the linear programming solvers. The pricing subproblems incorporate independent reliable shortest path problems and a knapsack problem. In numerical experiments, the proposed method can generate feasible solutions with good integrality gaps. [ABSTRACT FROM AUTHOR]

This paper concentrates on the mean-standard deviation shortest path problem, which is an important extension of traditional shortest path problem. Due to the standard deviation term, the general formulation of this problem is nonlinear and concave. We transform this formulation into a mixed-integer conic quadratic program and develop a generalized Benders decomposition approach. The Benders master problem is a continuous conic quadratic program about travel time mean and standard deviation. The subproblem is a least expected travel time path problem with the variance limit. At each iteration, the subproblem generates a generalized Benders optimality cut for the relaxed Benders master problem. The relaxed Benders master problem provides an ascending lower bound and the subproblem produces a feasible solution to update the upper bound. In the numerical experiments, all instances in four transportation networks are solved optimally. This paper provides a novel solving scheme for the mean-standard deviation shortest path problem. [ABSTRACT FROM AUTHOR]

• Study the full cover charging segment location problem with routing. • Formulate a location model with routing in space-time-electricity network. • Propose a column-based model and a column generation method. The driving range limitations and insufficient charging facilities impede the widespread application of electric vehicles. Generally, electric vehicles charge on static charging facilities (such as charging stations) for a long period and lose mobility during this period. With the development of charging-while-driving techniques, electric vehicles can recharge on the wireless charging segments without stopping. Given a set of origin-destination (OD) trips, the problem is to determine how many wireless charging segments we need and the exact distribution of these segments. Based on the space-time-electricity modeling framework, we formulate a novel full cover location model with routing to determine the number and distribution of charging segments. The battery capacity and travel time budget limitations can be naturally embedded and satisfied in the space-time-electricity network. We transform this model into an equivalent column-based model and develop a column-generation based decomposition approach. A set of independent pricing subproblems is solved by a time-dependent forward dynamic-programming algorithm. Numerical experiments are conducted on three transportation networks, showing that the proposed method can achieve good integrality gaps. Several parameters are analyzed including the number of OD trips, battery capacity, travel time budget, and charging speed of wireless charging segments. [ABSTRACT FROM AUTHOR]