Search

• Investigate assigning shipping requests to crowdsourcees with time and capacity constraints • Propose a centralized, deep reinforcement learning-based approach • Present new state space representation encompassing spatial-temporal and capacity information • Embed heuristics-guided action choice in DRL to preserve tractability and enhance efficiency • Integrate rule-interposing into DRL to further enhance training and implementation efficiency This paper investigates the problem of assigning shipping requests to ad hoc couriers in the context of crowdsourced urban delivery. The shipping requests are spatially distributed each with a limited time window between the earliest time for pickup and latest time for delivery. The ad hoc couriers, termed crowdsourcees, also have limited time availability and carrying capacity. We propose a new deep reinforcement learning (DRL)-based approach to tackling this assignment problem. A deep Q network (DQN) algorithm is trained which entails two salient features of experience replay and target network that enhance the efficiency, convergence, and stability of DRL training. More importantly, this paper makes three methodological contributions: 1) presenting a comprehensive and novel characterization of crowdshipping system states that encompasses spatial-temporal and capacity information of crowdsourcees and requests; 2) embedding heuristics that leverage information offered by the state representation and are based on intuitive reasonings to guide specific actions to take, to preserve tractability and enhance efficiency of training; and 3) integrating rule-interposing to prevent repeated visiting of the same routes and node sequences during routing improvement, thereby further enhancing the training efficiency by accelerating learning. The computational complexities of the heuristics and the overall DQN training are investigated. The effectiveness of the proposed approach is demonstrated through extensive numerical analysis. The results show the benefits brought by the heuristics-guided action choice, rule-interposing, and having time-related information in the state space in DRL training, the near-optimality of the solutions obtained, and the superiority of the proposed approach over existing methods in terms of solution quality, computation time, and scalability. [ABSTRACT FROM AUTHOR]

• Connect quadratic assignment model (QAP) with network design problem. • Reformulate time-dependent synchronized service design as network-based quadratic assignment problem. • Propose extended Gilmore-Lawler Bound (EGLB) in the generic QAP network. • Develop Branch & Bound algorithm with an effective lower bound estimator using EGLB. A new modeling framework is developed in this paper to design a class of synchronized transportation services that can be formulated as a time-dependent synchronized service network design problem. The framework is established using a generic network representation for the quadratic assignment problem (QAP). As one of the fundamental combinatorial optimization problems, the QAP was introduced by Koopmans and Beckman (KB-QAP), in 1957, in the context of locating economic activities. Our proposed network-based QAP (NET-QAP) model not only linearizes the KB-QAP model but also generalizes the traditional QAP model as a special case with a symmetric network structure. The NET-QAP is utilized to formulate a time-dependent synchronized service network design problem to obtain an optimal schedule for both inbound and outbound services in a transshipment area, where commodities are collected from origins using the inbound services and distributed to their final destinations using the outbound services (after sorting and storage). From the view of the Gilmore-Lawler Bound (GLB), this paper explores a new branch and bound framework to solve the synchronizing NET-QAP problem. An extended GLB (E-QAP) is adopted in this research as a lower bound estimator for the first-stage assignment costs, based on several relaxed subproblems in the second-stage assignment. Then, the framework can also be applied to estimate the cost of sub-decisions that are involved in making a broader decision-making problem. Numerical experiments are conducted to demonstrate the effectiveness and applicability of the proposed modeling and computational framework. [ABSTRACT FROM AUTHOR]

This paper studies a new variant of the vehicle routing problem with drones, i.e., the two-echelon vehicle routing problem with drones, where multiple vehicles and drones work collaboratively to serve customers. Drones can perform multiple back-and-forth trips when their paired vehicle stops at a customer node, forming a two-echelon network. Several practical constraints such as customers' delivery deadlines and drones' energy capacity are considered. Different from existing studies, we treat the number of drones taken by each vehicle as a decision variable instead of a given parameter, which provides more flexibility for planning vehicle and drone routes. We first formulate this problem as a mixed-integer linear programming model, which is solvable by off-the-shelf commercial solvers. To tackle instances more efficiently, we next construct a set-partitioning model. To solve it, an exact branch-and-price algorithm is proposed, where a bidirectional labeling algorithm is used to solve the pricing problem. To speed up the algorithm, a tabu search algorithm is first applied before the exact labeling algorithm for finding desired columns in each iteration of the column generation process. Extensive numerical tests show that our algorithm can solve most instances within 25 customers to optimality in a short time frame and some instances of 35 customers to optimality within a three-hour time limit. Results also demonstrate that the allocation decisions of drones can help save the duration of all routes by 3.44% on average for 25-customer instances, compared to the case of fixing the number of paired drones on each vehicle. In addition, sensitivity analyses show that multiple strategies, e.g., adopting batteries of a higher energy density and developing faster drones, can be applied to further improve the delivery efficiency of a truck–drone system. • A two-echelon vehicle routing problem with drones is studied. • The allocation decisions of drones to vehicles are considered. • An MILP model and a set-partitioning model are provided. • A branch-and-price algorithm is developed. • Results show the effectiveness of the algorithm and provide managerial insights. [ABSTRACT FROM AUTHOR]

• Investigate the inland depot location problem of the inland transportation system. • Build a robust mathematical model that focuses on determining when and where consignees/shippers are assigned to. • Propose a branch-and-price algorithm that is based on lagrangian relaxation and column generation. In this paper, we investigate the inland depot location problem of the inland transportation system. In inland container transportation, empty containers are transported between depots and consignees/shippers, and empty containers should be repositioned after/before inbound/outbound full containers. We build a robust mathematical model that focuses on determining when and where consignees/shippers are assigned to. In addition, inter-depots empty container repositioning is implemented considering demand uncertainty. This paper proposes a branch-and-price algorithm that is based on Lagrangian relaxation and column generation. We show the optimality condition of the pricing subproblem and construct a simpler formulation in this paper. Computational experiments are performed with test instances that mimic real life. Our results also show that considering time compatibility of full and empty container routes is closer to reality and increases the utilization of empty containers in depots. The proposed algorithm yields promising solutions compared with CPLEX. [ABSTRACT FROM AUTHOR]

The Electric Autonomous Dial-A-Ride Problem (E-ADARP) consists in scheduling a fleet of electric autonomous vehicles to provide ride-sharing services for customers that specify their origins and destinations. The E-ADARP considers the following perspectives: (i) a weighted-sum objective that minimizes both total travel time and total excess user ride time; (ii) the employment of electric autonomous vehicles and a partial recharging policy. This paper presents the first labeling algorithm for a path-based formulation of the DARP/E-ADARP, where the main ingredient includes: (1) fragment-based representation of paths, (2) a novel approach that abstracts fragments to arcs while ensuring excess-user-ride-time optimality, (3) construction of a sparser new graph with the abstracted arcs, which is proven to preserve all feasible routes of the original graph, and (4) strong dominance rules and constant-time feasibility checks to compute the shortest paths efficiently. This labeling algorithm is then integrated into Branch-and-Price (B&P) algorithms to solve the E-ADARP. In the computational experiments, the B&P algorithm achieves optimality in 71 out of 84 instances. Remarkably, among these instances, 50 were solved optimally at the root node without branching. We identify 26 new best solutions, improve 30 previously reported lower bounds, and provide 17 new lower bounds for large-scale instances with up to 8 vehicles and 96 requests. In total 42 new best solutions are generated on previously solved and unsolved instances. In addition, we analyze the impact of incorporating the total excess user ride time within the objectives and allowing unlimited visits to recharging stations. The following managerial insights are provided: (1) solving a weighted-sum objective function can significantly enhance the service quality, while still maintaining operational costs at nearly optimal levels, (2) the relaxation on charging visits allows us to solve all instances feasibly and further reduces the average solution cost. • We use a new paradigm to minimize (excess-)user-ride-time in the labeling algorithm. • Our CG algorithm optimizes 50 out of 84 instances at the root node. • Our CG algorithm obtains 24 better lower bounds than the best-reported results. • Our CG algorithm identifies 22 new best solutions and 15 new optimal solutions. • The B&P solves 71 out of 84 instances optimally and obtains 26 new best solutions. • The B&P obtains 30 better lower bounds compared to the best-reported results. • We investigate the impact of adding the total excess user ride time in the objectives. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents an overview of recovery models and algorithms for real-time railway disturbance and disruption management. This area is currently an active research area in Operations Research, including real-time timetable rescheduling and real-time rescheduling of the rolling stock and crew duties. These topics are addressed in this paper. Also research dealing with the integration of more than one rescheduling phase is discussed. Currently, the developed methods have been tested mainly in an experimental setting, thereby showing promising results, both in terms of their solution quality and in terms of their computation times. The application of these models and algorithms in real-life railway systems will be instrumental for increasing the quality of the provided railway services, leading to an increased utilization of the involved railway systems. [Copyright &y& Elsevier]

The paper illustrates a route choice model based on the recently proposed Combination of Random Utility Models (CoRUM) model by Papola (2016). Specifically, the CoRUM specification with nested logit components, termed Combination of Nested Logits (CoNL), accounts for any correlation patterns amongst alternatives while keeping a closed-form expression for both probabilities and correlations. Thus, the paper illustrates a CoNL route choice model capable to target correlations between routes based on their topological overlapping, and characterized by a closed-form probability statement. The CoNL route choice model is operationalized by means of an algorithm providing automatically CoNL specification and corresponding route choice probabilities on a set of enumerated paths. Model performance is tested on various networks, with very satisfactory results. [ABSTRACT FROM AUTHOR]

Airlines routinely use analytics tools to support flight scheduling, fleet assignment, revenue management, crew scheduling, and many other operational decisions. However, decision support systems are less prevalent to support strategic planning. This paper fills that gap with an original mixed-integer non-convex optimization model, named Airline Network Planning with Supply and Demand interactions (ANPSD). The ANPSD optimizes network planning (including route selection, flight frequencies and fleet composition), while capturing interdependencies between airline supply and passenger demand. We first estimate a demand model as a function of flight frequencies and network configuration, using a two-stage least-squares procedure fitted to historical data, and then formalize the ANPSD by integrating the empirical demand function into an optimization model. The model is formulated as a non-convex mixed-integer program. To solve it, we develop an exact cutting plane algorithm, named 2 α ECP, which iteratively generates hyperplanes to develop an outer approximation of the non-linear demand functions. Computational results show that the 2 α ECP algorithm outperforms state-of-the-art benchmarks and generates tight solution quality guarantees. A case study based on the network of a major European carrier shows that the ANPSD provides much stronger solutions than baselines that ignore – fully or partially – demand–supply interactions. • We propose an optimization model for airline network planning (ANPSD). • ANPSD captures demand-supply interactions with predictive-prescriptive analytics. • We develop an outer approximation scheme for mixed-integer non-convex programming. • The algorithm generates provably near-optimal solutions, outperforming benchmarks. • The solutions outperform baselines that ignore demand-supply interactions. [ABSTRACT FROM AUTHOR]

• An infrastructure-enabled autonomous driving system is explored. • A network user equilibrium model is developed for transportation networks with infrastructure-enabled autonomy. • Inconvenience costs due to transitions between autonomous driving and manual driving are explicitly modeled. Although autonomous vehicle (AV) technology is expected to bring dramatic societal, environmental, and economic benefits, the high vehicle cost might slow the adoption of AVs. This paper explores an infrastructure-enabled autonomous driving system, which is a promising remedy to the high cost of AVs. Specifically, the system combines vehicles and infrastructure in the realization of autonomous driving. Equipped with roadside sensing, computing, and communicating devices, an ordinary road can be upgraded into an " automated road " enabling autonomous driving service for vehicles with the minimum required on-board devices. The vehicle costs can thus be significantly reduced. We envision that automated roads will be deployed in transportation networks to serve a new type of vehicle called infrastructure-enabled autonomous vehicles (IEAVs), which can be driven autonomously only on automated roads but manually on ordinary roads. Therefore, IEAV users may experience inconvenience costs due to transitions between autonomous driving and manual driving, and the frequent switch will inevitably yield high inconvenience costs. Therefore, to minimize their individual travel cost, they have to decide whether to switch to the autonomous driving mode when heading to an automated road. Considering such a unique feature of IEAVs, we proposed a group of driving-mode-choice equilibrium conditions to describe IEAV drivers' driving mode choice behaviors, in which we considered drivers' travel time costs, service charges of autonomous driving, and inconvenience costs due to driving mode change. Combining traditional route-choice equilibrium conditions with the proposed driving-mode-choice equilibrium conditions, we developed a new user equilibrium (UE) model to describe the equilibrium flow distributions in a road network with automated roads and mixed-autonomy traffic. The UE model is formulated as a novel non-linear complementarity problem, and its solution existence is discussed. To solve the UE model, a network expansion method is proposed to reformulate the UE model as a standard path-based UE model. A route-swapping-based solution algorithm is then used to solve the reformulated UE model. Numerical studies are presented to demonstrate the proposed models and algorithms. [ABSTRACT FROM AUTHOR]

This paper investigates a new variant of the consistent vehicle routing problem considering path consistency based on the underlying road network (ConVRP R N). It is the problem of determining a set of consistent paths for vehicles within a certain period (e.g. a week). We propose a flexible strategy to achieve path consistency, providing a discount for the cost of roads that are traversed every day. The objective is to minimize the total travel costs considering the discount for the paths' consistent parts. We formulate the problem as a set partitioning model and a general arc-flow model, and then solve the problem by a branch-price-and-cut algorithm. The algorithm is based on a two-layer network, including an underlying road-network graph (lower layer) and a serial of customer-based graphs (upper layer). Furthermore, an innovative aggregation technique is proposed to accelerate the algorithm, which is specifically designed for ConVRP R N. Finally, we construct a road network based on the real road-network structure of West Jordan and demonstrate the effectiveness of our approach on a set of numerical experiments. The impact of consistency discount is also analyzed to provide information and inspiration for tactical decision making. • A new variant of the consistent VRP considering road network information and imposing path consistency is proposed. • A coupled two-layer network is constructed to consider road network information within a branch-price-and-cut framework. • An innovative aggregation technique is customized to speed up the branch-price-and-cut algorithm. • A set of numerical experiments based on a real-world road network are implemented. [ABSTRACT FROM AUTHOR]

The modelling of vehicle emissions within Traffic Assignment (TA) has been studied in the literature as emissions such as carbon monoxide and carbon dioxide are detrimental to the populace's health as well as to the environment. TA is employed as a means to identify the potential to reduce vehicle emissions by obtaining emissions-minimising traffic patterns. TA captures the flow-dependent cost to traverse an arc in a so-called arc cost function, which often captures travel time, travel cost, or emissions. Arc cost functions that model emissions are naturally non-monotonic (partly increasing and partly decreasing) with respect to arc flow. Studies that make use of emission-based arc cost functions in TA generally assume a positive, increasing function, or do not discuss the computational complexities that arise when the arc cost functions are non-monotonic. In this paper, we investigate the implications of non-monotonic arc costs within the TA methodology and address the complexity of the resulting problem. We suggest adjustments to solution algorithms to heuristically allow the computation of TA solutions with non-monotonic arc costs. We present several methods to find good solutions to the TA problem with non-monotonic arc costs in the absence of a unique emissions-minimising solution. We compare these methods by applying them to several test networks for non-monotonic arc cost functions that model different emission types. • We study the traffic assignment (TA) with non-monotonic arc costs (SONM), in the context of emissions. • We show that when arc-cost functions meet certain criteria, the SONM problem is NP-Hard. • We propose a solution algorithm to the SONM problem. • We present computational results for real-world TA instances. [ABSTRACT FROM AUTHOR]

We propose a Recursive Logit (STD-RL) model for routing policy choice in a stochastic time-dependent (STD) network, where a routing policy is a mapping from states to actions on which link to take next, and a state is defined by node, time and information. A routing policy encapsulates travelers' adaptation to revealed traffic conditions when making route choices. The STD-RL model circumvents choice set generation, a procedure with known issues related to estimation and prediction. In a given state, travelers make their link choice maximizing the sum of the utility of the outgoing link and the expected maximum utility until the destination (a.k.a. value function that is a solution to a dynamic programming problem). Existing recursive route choice models and the corresponding solution approaches are based on the assumption that network attributes are deterministic. Hence, they cannot be applied to stochastic networks which are the focus of this paper. We propose an efficient algorithm for solving the value function and its gradient, critical for parameter estimation. It is based on partitioning the state space and decomposing costly matrix operations into a series of simpler ones. We present numerical results using a synthetic network and a network in Stockholm, Sweden. The estimation running time has a 20-30 times speed-up due to matrix decomposition. The estimated model parameters have realistic interpretations. Specifically, travelers are more likely to be adaptive to realized travel times during a longer trip, and more sensitive to travel time when travel time variability is higher. The STD-RL model performs better in predicting route choices than the RL model in a corresponding static and deterministic network. • A recursive logit (STD-RL) model for routing policy choice in stochastic networks. • A decomposition scheme to tackle a non-linear system with a large state space. • Potential biases due to ignored stochasticity identified by synthetic data analysis. • STD-RL achieves better prediction than a deterministic model in a Stockholm case study. [ABSTRACT FROM AUTHOR]

This paper is motivated by recent results in the design of signal plans for Manhattan that highlight the importance of providing signal control algorithms with an analytical description of between-link dependencies. This is particularly important for congested networks prone to the occurrence of spillbacks. This paper formulates a probabilistic network model that proposes an aggregate description of the queue-length, and then approximates the joint aggregate queue-length distribution of subnetworks. The goal is to model between-queue dependencies beyond first-order moments, yet to do so in a tractable manner such that these techniques can be used for optimization purposes. This paper models an urban road network as a finite space capacity Markovian queueing network. Exact evaluation of the stationary joint queue-length distribution of such a network with arbitrary size and topology can be obtained numerically. Nonetheless, the main challenge to such an approach remains the dimensionality of the network state space, which is exponential in the number of queues. This paper proposes to address the dimensionality issue by: 1) describing the state of the network aggregately, and 2) decomposing the network into overlapping subnetworks. We propose an analytical approximation of the stationary aggregate joint queue-length distribution of a subnetwork. The model consists of a system of nonlinear equations with a dimension that is linear, instead of exponential, in the number of queues and that is independent of the space capacity of the individual queues. The method is derived for tandem Markovian finite capacity queueing networks. The proposed model is computationally tractable and scalable, it can be efficiently used for the higher-order distributional analysis of large-scale networks. The model is validated versus simulation estimates and versus other decomposition methods. We then use it to address an urban traffic control problem. We show the added value of accounting for higher-order spatial between-queue dependency information in the control of congested urban networks. [ABSTRACT FROM AUTHOR]

Platooning connected and autonomous vehicles (CAVs) can improve traffic and fuel efficiency. However, scalable platooning operations require junction-level coordination, which has not been well studied. In this paper, we study the coordination of vehicle platooning at highway junctions. We consider a setting where CAVs randomly arrive at a highway junction according to a general renewal process. When a CAV approaches the junction, a system operator determines whether the CAV will merge into the platoon ahead according to the positions and speeds of the CAV and the platoon. We formulate a Markov decision process to minimize the discounted cumulative travel cost, i.e., fuel consumption plus travel delay, over an infinite time horizon. We show that the optimal policy is threshold-based: the CAV will merge with the platoon if and only if the difference between the CAV's and the platoon's predicted times of arrival at the junction is less than a constant threshold. We also propose two ready-to-implement algorithms to derive the optimal policy. Comparison with the classical value iteration algorithm implies that our approach explicitly incorporating the characteristics of the optimal policy is significantly more efficient in terms of computation. Importantly, we show that the optimal policy under Poisson arrivals can be obtained by solving a system of integral equations. We also validate our results in simulation with a Real-time Strategy (RTS) using real traffic data. The simulation results indicate that the proposed method yields better performance compared with the conventional method. • The Markov decision process is formulated to minimize discounted cumulative travel cost. • The optimal coordination platooning policy is threshold-based. • Incorporating identified policy characteristics can improve algorithm efficiency. • The policy is implemented in Real-time Strategy by dynamic flow prediction. [ABSTRACT FROM AUTHOR]

• Formulated continuous approximation model for optimizing AB-type skip-stop service under heterogeneous demand. • Developed an efficient algorithm that solves the model to near-optimality. • Proposed a recipe for fitting the continuous approximation solution to real settings. • AB-type service outperforms all-stop service under various operating conditions. Transit vehicles operating under skip-stop service visit only a subset of the stops residing along a corridor. It is a strategy commonly used to increase vehicle speeds and reduce patron travel times. The present paper develops a continuous approximation model to optimally design a select form of skip-stop service, termed AB-type service. The model accounts for demand patterns that slowly vary over space. An efficient heuristic is developed to obtain solutions. These are shown to be near-optimal for a variety of numerical examples. Results also indicate that optimal AB-type designs outperform optimized all-stop service in a variety of cases. The AB-type service is found to be especially competitive when travel demands are high, trip origins are unevenly distributed along a corridor, and patrons have relatively high values of time. In these cases, AB-type service is found to reduce system costs by as much as 8%. [ABSTRACT FROM AUTHOR]

• Propose the concepts of line strategy (LS) and node strategy (NS) and a novel methodology adopting the decision variables of LS and NS proportions. • Impose transfer constraints explicitly and mix all the passengers with the same maximal number of transfers together. • Establish the LNS (line and node strategy) -based model on the original transit networks and reduce the scope of the feasible transfer nodes by the maximal transfer constraints. • Adopt both the method of successive averages (MSA) and a projection algorithm to solve the LNS-based model. • The performance of the LNS-based model and algorithm on a transit subnetwork of Beijing showcases its huge advantage. Passengers traveling on transit networks involve two kinds of decision-making strategies: deciding which lines are attractive at an origin or transfer node (denoted line strategy, LS), or deciding which node to transfer at when riding a line (denoted node strategy, NS). Combining these two strategies, this paper proposes a novel variational inequality formulation for the user equilibrium passenger assignment problem. The inclusion of the NS eliminates the need for passenger assignment on a large augmented graph, reducing the modeling complexity and making it easier to track all passengers' travel routes. Moreover, constraints on the maximal number of transfers—which are crucial in practical decision-making on transit networks—are explicitly included, further drastically reducing the set of passengers' feasible strategies. Furthermore, some extant strategy-based transit assignment models are shown to be a special case of the proposed model when the transfer constraint is removed. Finally, the properties of the proposed model are illustrated on a small network, and the model and algorithm exhibit huge advantages on the chosen transit subnetwork of Beijing. [ABSTRACT FROM AUTHOR]

• Dynamic user equilibrium (DUE) path delays may be realistically described as weakly monotone increasing (WMI), and inverse travel demand functions may be realistically described as strongly monotone decreasing (SMD). • We establish convergence of fixed-point DUE algorithms under the conditions of Lipschitz continuity, WMI path delays, and SMD inverse travel demand functions. • We provide a detailed numerical example showing that the assumptions of Lipschitz continuity, WMI path delays, and SMD inverse travel demand functions hold along the feasible trajectory of fixed-point iterates en route to a DUE solution. In this paper we present sufficient conditions for convergence of projection and fixed-point algorithms used to compute dynamic user equilibrium with elastic travel demand (E-DUE). The assumption of strongly monotone increasing path delay operators is not needed. In its place, we assume path delay operators are merely weakly monotone increasing, a property assured by Lipschitz continuity, while inverse demand functions are strongly monotone decreasing. Lipschitz continuity of path delay is a very mild regularity condition. As such, nonmonotone delay operators may be weakly monotone increasing and satisfy our convergence criteria, provided inverse demand functions are strongly monotone decreasing. We illustrate convergence for nonmonotone path delays via a numerical example. [ABSTRACT FROM AUTHOR]

With unbalanced travel demand distribution over time and space, a stationary cordon location hinders the full potential of perimeter flow control based on network Macroscopic Fundamental Diagram (MFD). This paper introduces a perimeter control method wherein the region boundaries alter in real-time to tackle propagation of local pockets of congestion. The nonlinear dynamics of the heterogeneous traffic network are modelled as a switching system. The linearization of the derived switching nonlinear dynamics is conducted considering the accumulation heterogeneity. A Linear Quadratic Regulator (LQR) is employed for gating the flow exchange between regions to minimize network congestion. Several scenarios are examined comparing perimeter control schemes with static and dynamic cordons. Results pinpoint the proposed LQR control with location-varying cordon strategy and a moderate switching interval significantly reduces the vehicles total time spent in the network. • We develop a perimeter control method based on MFD wherein the region boundaries alter. • Splitting the congested and uncongested regions is revisited recurrently in real-time. • We propose a novel traffic-responsive cordon switching algorithm integrated within a location-varying perimeter control method. • Modelling the nonlinear dynamics of the heterogeneous traffic network as a switching system. • The linearization of the derived switching nonlinear dynamics considers the accumulation heterogeneity. • A Linear Quadratic Regulator is employed for gating the flow exchange between regions. [ABSTRACT FROM AUTHOR]

• Develop a Nash game for two CAVs independently passing an unsignalised intersection. • Explore the two-CAV cooperative control mechanism for an unsignalised intersection. • Extend the game-theoretical analysis to a n-player case where n > 3. • Tailor an efficient branch & bound algorithm to solve the developed game models. • Reveal some generalized insights from different control mechanisms. We in this paper investigate navigation strategies of two cross-moving connected and autonomous vehicles (CAVs) at an unsignalised intersection. As highly intelligent and automated entities, CAVs could make decisions independently or behave in a cooperative manner. A Nash game with discrete decision strategy is formulated to characterize the non-cooperative behaviour and a cooperative game is formulated to model the cooperative control mechanism. Results show that (i) pure-strategy Nash equilibria (NEs) for the non-cooperative game always exist and NEs hold if and only if at least one CAV takes its dominant strategy; (ii) more than two pure-strategy NE solutions may exist, but at most two different payoffs could arrive for each player at pure-strategy NEs; (iii) the optimal solution to the cooperative game must be in the NE solution set. These interesting findings provide useful managerial insights to CAV operators and transport authorities, and also enable us to tailor a branch & bound (B&B) algorithm to efficiently solve the models. We also extend the proposed methodology to the n-player case (n ≥ 3) and give some more generalized insights. Numerical experiments are demonstrated in the end to test the computational accuracy and efficiency of the B&B method and show that our models and algorithm can be readily incorporated into future real-time CAV decision system to help navigate through unsignalised intersections. [ABSTRACT FROM AUTHOR]

This paper investigates a local container drayage problem with controllable vehicle interference (LCDP&CVI) under the tractor-and-trailer separation mode in which a tractor can be coupled or decoupled with a trailer at a customer location or a terminal. The container drayage requests proposed by customers should be fulfilled by a set of vehicle fleets, and each vehicle fleet comprises of a certain number of tractors and trailers that should be matched to each other. The controllable vehicle interference (CVI) means that the routes of any tractors from different vehicle fleets are independent of each other, implying that the interference between tractors is restricted only to the tractors from the same vehicle fleets. A mixed-integer linear programming (MILP) model is proposed for the LCDP&CVI. To exactly solve the problem, we develop a branch-price-and-cut algorithm based on the reformation of the MILP model, including a master problem and a pricing sub-problem. The pricing sub-problem that deals with the temporal synchronization constraints is formulated as the multi-vehicle shortest path problem with interference. By adding the tractor to the temporal-spatial network, a new representation of the pricing sub-problem is constructed, which enables us to solve the sub-problem by the multi-label method. In addition, the symmetrical elimination and dominance rules are incorporated into the multi-label method to enhance its effectiveness. Extensive numerical experiments are conducted to validate the proposed model and solution algorithm. For small-scale instances, the proposed solution algorithm is able to solve instances with up to 24 requests to optimality within two hours, which outperforms significantly the commercial MILP solver in terms of efficiency and effectiveness. For large-scale instances, the proposed algorithm can yield competitive solutions that are superior to the heuristic algorithms reported in the literature. Our experimental results also show that the controllable vehicle mechanism can strike a good balance between computational efficiency and operational costs by meticulously designing the structure of vehicle fleets. • We investigate a local container drayage problem with controllable vehicle interference under the tractor-and-trailer separation mode. • We develop a branch-price-and-cut algorithm to solve the problem. The temporal interdependency among tractors is considered in the pricing sub-problem, and the sub-problem is formulated as the multi-vehicle shortest path problem with interference. • We present a new graphical representation to reformulate the sub-problem for multi-label solving, enhancing effectiveness with symmetry elimination and tailored dominance rules. • We conduct extensive computational experiments on the randomly distributed instances and the cluster-distributed instances to validate the proposed model and solution algorithm. [ABSTRACT FROM AUTHOR]

This paper analyzes dynamic user equilibrium (DUE) that incorporates the notion of boundedly rational (BR) user behavior in the selection of departure times and routes. Intrinsically, the boundedly rational dynamic user equilibrium (BR-DUE) model we present assumes that travelers do not always seek the least costly route-and-departure-time choice. Rather, their perception of travel cost is affected by an indifference band describing travelers’ tolerance of the difference between their experienced travel costs and the minimum travel cost. An extension of the BR-DUE problem is the so-called variable tolerance dynamic user equilibrium (VT-BR-DUE) wherein endogenously determined tolerances may depend not only on paths, but also on the established path departure rates. This paper presents a unified approach for modeling both BR-DUE and VT-BR-DUE, which makes significant contributions to the model formulation, analysis of existence, solution characterization, and numerical computation of such problems. The VT-BR-DUE problem, together with the BR-DUE problem as a special case, is formulated as a variational inequality. We provide a very general existence result for VT-BR-DUE and BR-DUE that relies on assumptions weaker than those required for normal DUE models. Moreover, a characterization of the solution set is provided based on rigorous topological analysis. Finally, three computational algorithms with convergence results are proposed based on the VI and DVI formulations. Numerical studies are conducted to assess the proposed algorithms in terms of solution quality, convergence, and computational efficiency. [ABSTRACT FROM AUTHOR]

• Consider a practical ship routing problem with COA selection and uncertain voyage costs. • Develop a tailored branch-and-price-and-cut solution approach. • Conduct extensive numerical experiments to test the performance of the algorithm and analyze the value of robust optimization. Maritime transportation forms the backbone of the world merchandise trade. In this paper, we consider a problem that combines three interconnected subproblems in tramp shipping: the fleet adjustment problem, the cargo selection problem, and the ship routing problem. For cargo selection, we consider the decision behaviors under the setting of Contract of Affreightment (COA), in which cargoes should be rejected or accepted as a batch. In view of the uncertainties observed in maritime transportation, we formulate the problem in a robust way so that the solutions can protect the profitability of shipping companies against variations in voyage costs. We first provide compact mixed integer linear programming formulations for the problem and then convert them into a strengthened set covering model. A tailored branch-and-price-and-cut algorithm is developed to solve the set covering model. The algorithm is enhanced by a multi-cut generation technique aimed at tightening the lower bounds and a primal heuristic aimed at finding high-quality upper bounds. Extensive computational results show that our algorithm yields optimal or near-optimal solutions to realistic instances within short computing times and that the enhancement techniques significantly improve the efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

• We present a polynomial algorithm for user-based relocation and vehicle dispatching. • We solve instances with 100,000 requests and 10,000 vehicles in less than 4 min. • We show that spatial relocation outperforms temporal relocation. • We analyze the impact of discount strategies on user comfort. Free-floating car sharing (FFCS) systems are a promising concept to reduce the traffic volume in cities. However, spatial and temporal mismatches of supply and demand require a relocation of rental cars in order to avoid low degrees of utilization. Here, especially user-based relocation strategies seem to be promising to increase utilization in a cost-efficient manner. However, a thorough optimization-based assessment of user-based relocation strategies for FFCS systems is still missing. In this paper, we introduce an integer program that optimizes the assignment of user-based relocation strategies in FFCS fleets. We develop a graph representation that allows to reformulate the problem as a k-disjoint shortest paths problem and propose an exact algorithm to solve large-size instances. We show that this algorithm can solve real-world instances within a few milliseconds as well as instances with up to 100,000 customers and 10,000 vehicles in a few minutes. Furthermore, we present a case study based on real-world data and derive managerial insights on user-based relocation strategies. Our results reveal an upper bound on the benefit of user-based relocation strategies and demonstrate that the employment of such strategies can increase the number of fulfilled rental requests by 21%, while increasing the operator's revenue by 10%. [ABSTRACT FROM AUTHOR]

• Local optimality is suggested as a criterion to characterize route choice candidates. • Locally optimal routes have a mechanistic justification and require minimal data. • An algorithm to find locally optimal routes is presented and tested. • The approach is efficient in large systems, facilitates comprehensive traffic models. • Locally optimal routes yield good predictions of where travellers can be observed. Route choice is often modelled as a two-step procedure in which travellers choose their routes from small sets of promising candidates. Many methods developed to identify such choice sets rely on assumptions about the mechanisms behind the route choice and require corresponding data sets. Furthermore, existing approaches often involve considerable complexity or perform many repeated shortest path queries. This makes it difficult to apply these methods in comprehensive models with numerous origin-destination pairs. In this paper, we address these issues by developing an algorithm that efficiently identifies locally optimal routes. Such paths arise from travellers acting rationally on local scales, whereas unknown factors may affect the routes on larger scales. Though methods identifying locally optimal routes are available already, these algorithms rely on approximations and return only few, heuristically chosen paths for specific origin-destination pairs. This conflicts with the demands of route choice models, where an exhaustive search for many origins and destinations would be necessary. We therefore extend existing algorithms to return (almost) all admissible paths between a large number of origin-destination pairs. We test our algorithm and its applicability in route choice models on the road network of the Canadian province British Columbia and empirical data collected in this province. [ABSTRACT FROM AUTHOR]

• We address the real-time railway traffic management for large-scale networks microscopically. • We propose three decomposition methods, based on geography, trains, and time intervals, to partition a large-scale problem into some small-scale subproblems. • We present three distributed optimization approaches, namely ADMM, PR, and CDRSBK, for achieving the coordination of subproblems. • The proposed CDRSBK algorithm in the case of the train-based decomposition can find an optimal or near-optimal solution within 10 s of computation time. This paper introduces decomposition and distributed optimization approaches for the real-time railway traffic management problem considering microscopic infrastructure characteristics, aiming at an improved computational efficiency when tackling large-scale railway networks. Based on the nature of the railway traffic management problem, we consider three decomposition methods, namely a geography-based (GEO) decomposition, a train-based (TRA) decomposition, and a time-interval-based (TIN) decomposition, in order to partition the large railway traffic management optimization problem into several subproblems. In particular, an integer linear programming (ILP) model is developed to generate the optimal GEO solution, with the objectives of minimizing the number of interconnections among regions and of balancing the size of regions. The decomposition creates couplings among the subproblems, in terms of either capacity usage or transit time consistency; therefore the whole problem gets a non-separable structure. To handle the couplings, we introduce three distributed optimization approaches, namely an Alternating Direction Method of Multipliers (ADMM) algorithm, a priority-rule-based (PR) algorithm, and a Cooperative Distributed Robust Safe But Knowledgeable (CDRSBK) algorithm, which operate iteratively. We test all combinations of the three decomposition methods and the three distributed optimization algorithms on a large-scale railway network in the South-East of the Netherlands, in terms of feasibility, computational efficiency, and optimality. Overall the CDRSBK algorithm with the TRA decomposition performs best, where high-quality (optimal or near-optimal) solutions can be found within 10 s of computation time. [ABSTRACT FROM AUTHOR]

• A novel model of loop metro service driven by stochastic demand of general distribution. • A Markov decision process for optimal schedule with circulation of limited rolling stock. • An actor-critic deep reinforcement learning framework with an off-policy training algorithm. • A case study demonstrating the efficiency and robustness of the proposed control system. This paper presents a novel actor-critic deep reinforcement learning approach for metro train scheduling with circulation of limited rolling stock. The scheduling problem is modeled as a Markov decision process driven by stochastic passenger demand. As in most dynamic optimization problems, the complexity of the scheduling process grows exponentially with the amount of states, decisions, and uncertainties involved. This study aims to address this 'curses of dimensionality' issue by adopting an actor-critic deep reinforcement learning solution framework. The framework simplifies the evaluation and searching process for potential optimal solutions by parameterizing the original state and decision spaces with the use of artificial neural networks. A deep deterministic policy gradient algorithm is developed for training the artificial neural networks via simulated system transitions before the actor-critic agent can be applied for online schedule control. The proposed approach is tested with a real-world scenario configured with data collected from the Victoria Line of London Underground, UK. Experiment results illustrate the advantages of the proposed method over a range of established meta-heuristics in terms of computing time, system efficiency, and robustness under different stochastic environments. This study innovates urban transit operations with state-of-the-art computer science and dynamic optimization techniques. [ABSTRACT FROM AUTHOR]

• formulate and study a new and practical variant of static bike-sharing re-positioning problem (BSRP) with multiple vehicle depots and comprehensive objective function of traveling cost minimization and inventory cost minimization. • propose an effective clustering strategy that enables decomposition of the original problem into classical traveling salesman problem and multi-depot vehicle routing problem. • design tailored destroy-and-repair algorithm to conduct clustering optimization, and adaptive variable neighborhood search for routing optimization. • perform extensive computational studies to validate performance of the proposed algorithm, which demonstrates the algorithm's competitiveness in solving large-scale BSRPs when compared with CPLEX and state-of-the-art algorithms. This paper studies the bike-sharing re-positioning problem (BSRP) frequently encountered in modern bike-sharing systems that are widely deployed around the world. To cope with customer demand fluctuations and improve service level, BSRP aims to identify the optimal vehicle routes to visit bike-sharing stations in order to balance their inventories, picking up excess bikes from surplus stations and adding needed bikes to insufficient stations, with the objective of minimizing total traveling cost and inventory cost. The mathematical model of the studied problem is first given, detailing the considerations of multiple depots available for re-positioning vehicles and the extra objective of inventory cost minimization. An effective clustering strategy is then proposed to put bike-sharing stations into self-sufficient groups, which is shown to be able to greatly decompose the problem complexity for large-scale instances. A destroy-and-repair algorithm is developed to improve the clusters, and an adaptive variable neighborhood search algorithm is designed to conduct intra-cluster and inter-cluster vehicle routing optimization. Performance of the hybrid algorithm is validated on three sets of benchmark instances, and compared with CPLEX as well as state-of-the-art algorithms from the literature, which demonstrates that the proposed algorithm is highly competitive in solving BSRPs. [ABSTRACT FROM AUTHOR]

• The first to formulate a multi-trip drone routing problem. • Logical cuts and subgradient cuts for nonlinear energy function. • 2-index formulation and branch-and-cut algorithm. • Benchmark instance sets based on realistic parameters and known instance sets. • Numerical tests demonstrate the effectiveness of modeling and solution schemes. Drone delivery is known as a potential contributor in improving efficiency and alleviating last-mile delivery problems. For this reason, drone routing and scheduling has become a highly active area of research in recent years. Unlike the vehicle routing problem, however, designing drones' routes is challenging due to multiple operational characteristics including multi-trip operations, recharge planning, and energy consumption calculation. To fill some important gaps in the literature, this paper solves a multi-trip drone routing problem, where drones' energy consumption is modeled as a nonlinear function of payload and travel distance. We propose adding logical cuts and subgradient cuts in the solution process to tackle the more complex nonlinear (convex) energy function, instead of using the linear approximation method as in the literature, which can fail to detect infeasible routes due to excess energy consumption. We use a 2-index formulation to model the problem and develop a branch-and-cut algorithm for the formulation. Benchmark instances are first generated for this problem. Numerical tests indicate that even though the original model is nonlinear, the proposed approach can solve large problems to optimality. In addition, in multiple instances, the linear approximation model yields routes that under the nonlinear energy model would be energy infeasible. Use of a linear approximation for drone energy leads to differences in energy consumption of about 9% on average compared to the nonlinear energy model. [ABSTRACT FROM AUTHOR]

• A tighter lower bound is proposed. • Machine learning-driven upper bounds are proposed. • An exact algorithm based on the enhanced upper bounds is proposed. • A heuristic is proposed to tackle large-scale instances. • The performance of the proposed algorithms is validated through benchmark data. The container relocation problem is one of important issues in seaport terminals which could bring a significant saving on the operating cost even with a slight improvement due to the huge number of containers processed across the world each year. Given a specific layout and container retrieval priorities, the container relocation problem aims to find the optimal movement sequence to minimize the total number of container relocation operations. In this paper, we propose novel machine learning-driven algorithms, which integrate optimization methods and machine learning techniques, to solve the problem. More specifically, we propose a new upper bound method called MLUB that incorporates branch pruners. These pruners are derived from some machine learning techniques through using the optimal solution values of many small-scale instances. The tightened upper bounds generated by MLUB are used subsequently both in the exact branch-and-bound algorithm called IB&B and the hybrid beam search heuristic called MLBS. Moreover, we also provide a tighter lower bound for the problem by additionally considering the interaction between consecutive target containers. Based on the benchmark data published recently in the literature, extensive experiments are conducted to test the performance of the proposed algorithms. The experimental results demonstrate that the proposed algorithms outperform the state-of-the-art algorithms reported in the literature, and some managerial insights regarding the load intensity of the bay and some algorithm parameters such as the look-ahead depth and the beam width are drawn from the results. [ABSTRACT FROM AUTHOR]

• Propose MD-MT-MPPDTW as a new problem variant towards delivery-as-a-service. • Propose an MIP model that is solvable for MD-MT-MPPDTW. • Propose a hybrid meta-heuristic to combine the merits of ALNS and Tabu search. • Propose a two-level pruning strategy to significantly speedup the search procedure. • Conduct extensive experiments to verify the effectiveness of the proposed algorithm. In this paper, we investigate a new variant of last-mile delivery that integrates the scheduling of static E-commerce parcels and Online-to-Offline(O2O) parcels. The O2O parcels, such as flowers and cakes, are often delivered intra city with a time window constraint. It is driven by the concept of delivery-as-a-service, which targets at building consolidated infrastructure and using the same fleet of vehicles to provide standardized delivery services for different types of merchants. We formulate it as an integration of Multi-Depot Multi-Trip Vehicle Routing Problem (MDMTVRP) and Paired Pickup and Delivery Problem with Time Window (PPDPTW). To solve the mixed problem of MDMTVRP and PPDPTW, we present its Mixed-Integer Programming (MIP) model to obtain the optimal solution for small-scale instances. To solve large-scale problems, we propose a hybrid neighborhood search strategy to effectively combine the merits of ALNS and tabu search. We also present a two-level pruning strategy that can significantly accelerate the local search procedure. We conduct extensive numeric experiments on multiple datasets, and results showed that our hybrid approach achieved near-optimal performance and established clear superiority over ALNS and tabu search. [ABSTRACT FROM AUTHOR]

• Data-driven Bayesian network classifier as a real-time predictor of the coming ships for PSC inspection. • Dynamic programming for optimal discretization the input data in the TAN classifier. • Prove random selection of root attribute variable in the TAN classifier will not influence the classification process. • Identify the sub-standard ships with more deficiencies more accurately compared with the currently used Ship Risk Profile ship selection scheme. Maritime transportation plays a pivotal role in the economy and globalization, while it poses threats and risks to the maritime environment. In order to maintain maritime safety, one of the most important mitigation solutions is the Port State Control (PSC) inspection. In this paper, a data-driven Bayesian network classifier named Tree Augmented Naive Bayes (TAN) classifier is developed to identify high-risk foreign vessels coming to the PSC inspection authorities. By using data on 250 PSC inspection records from Hong Kong port in 2017, we construct the structure and quantitative parts of the TAN classifier. Then the proposed classifier is validated by another 50 PSC inspection records from the same port. The results show that, compared with the Ship Risk Profile selection scheme that is currently implemented in practice, the TAN classifier can discover 130% more deficiencies on average. The proposed classifier can help the PSC authorities to better identify substandard ships as well as to allocate inspection resources. [ABSTRACT FROM AUTHOR]

This paper addresses a pickup and delivery problem with crowdsourced bids and transshipment (PDPCBT) in last-mile delivery, where all requests can be satisfied by either using the own vehicle fleet or outsourcing with a small compensation to crowdshippers through transshipment facilities. The crowdshippers show their willingness to deliver by submitting bids to the e-commerce company. To minimize both the travel cost of vehicles and the compensation of crowdshippers, the routes of vehicles and the selection of bids need to be optimized simultaneously. We formulate the PDPCBT into an arc-based formulation and a route-based formulation, where the latter is strengthened by the subset row inequalities. Based on the route-based formulation, we present a branch-and-price-and-cut algorithm to solve it exactly. To deal with two possible ways of serving requests, we first decompose the corresponding pricing problem into a shortest path problem and a knapsack problem, and then tackle them in the same bi-directional labeling algorithm framework. We also discuss acceleration techniques and implementation details to speed up the performance of the overall procedure. Computational experiments are conducted on a set of classic request instances, together with a set of randomly generated bid instances. With a time limit of two hours, numerical results validate the efficiency and effectiveness of the proposed algorithm. Finally, sensitivity analysis and managerial findings are also provided on the PDPCBT. • Present a tight route-based formulation for the pickup and delivery problem with crowdsourced bids and transshipment. • Propose an exact branch-and-price-and-cut algorithm to solve the model. • Design several acceleration techniques for the exact algorithm. • Introduce valid inequalities to lift the lower bound. • Demonstrate the efficiency of the proposed algorithm in extensive experiments. [ABSTRACT FROM AUTHOR]

Abstract: This paper addresses the toll design problem of finding the toll locations and levels in a congestion pricing scheme, which minimize the total travel time and the toll-point cost (set-up and operational costs of the toll collecting facilities). Road users in the network are assumed to be distributed according to the principle of user equilibrium, with the demand assumed to be fixed and given a priori. The toll design problem is commonly formulated as a non-linear program, which in general is non-convex and non-smooth, and thus difficult to solve for a global optimum. In this paper, the toll design problem is approximated by a mixed integer linear program (MILP), which can be solved to its globally optimal solution. The MILP also gives a lower bound estimation of the original non-linear problem, and the accuracy of the approximation is improved by iteratively updating the MILP. To demonstrate the approach, we apply the algorithm to two networks: a smaller network with 18 links and 4 OD-pairs to illustrate the properties of the approach, and the Sioux Falls network with 87 links and 30 OD-pairs to demonstrate the applicability of the approach. [Copyright &y& Elsevier]

• Event-based solution scheme for the (general) link transmission model. • On-the-fly inner linearization technique to simplify expansion fans in a general network setting. • Event-based multi-commodity support framework for different types of commodities such as path based or departure time period based approaches. • Within iteration route choice support in an event-based macroscopic network loading setting. • Case studies on general network demonstrating suitability and feasibility of the proposed solution scheme for large scale planning purposes. In this paper a novel solution algorithm is proposed for solving general first order dynamic network loading (DNL) problems in general transport networks. This solution algorithm supports any smooth non-linear two regime concave fundamental diagram and adopts a simplified fanning scheme. It is termed eGLTM (event-based General Link Transmission Model) and is based on a continuous-time formulation of the kinematic wave model that adapts shockwave theory to simplify expansion fans. As the name suggests eGLTM is a generalisation of eLTM, which is a special case that solves the simplified first order model assuming a triangular fundamental diagram. We analyse the impact of modelling delay in the hypocritical branch of the fundamental diagram to assess the differences between the two models. In addition, we propose an additional stream of mixture events to propagate multi-commodity flow in event based macroscopic models, which makes both eLTM and eGLTM suitable for dynamic traffic assignment (DTA) applications. The proposed solution scheme can yield exact solutions as well as approximate solutions at a significantly lesser cost. The efficiency of the model is demonstrated in a number of case studies. Furthermore, different settings for our simplified fanning scheme are investigated as well as an extensive analysis on the effect of including route choice on the algorithms computational cost. Finally, a large scale case study is conducted to investigate the suitability of our newly proposed model in a practical context and assess its efficiency. In this study comparisons between eLTM and eGLTM are included to demonstrate the impact of aforementioned generalisation as well as the multi-commodity extension that is proposed. [ABSTRACT FROM AUTHOR]

Highlights • Formulating a signal timing optimization program with explicit representation of the cell transmission model flow-density diagram to avoid the flow holding-back problem. • Developing an algorithm based on the Benders decomposition technique to convert the original MINLP to an IP and several CTM simulation runs. • Proving the optimality, convergence, and feasibility properties of the solution technique. • Developing a dual estimation algorithm for the MINLP to generate Benders cuts with a simulation-based approach. Abstract This paper formulates the network-level traffic signal timing optimization problem as a Mixed-Integer Non-Linear Program (MINLP) and presents a customized methodology to solve it with a tight optimality gap. The MINLP is based on the Cell Transmission Model (CTM) network loading concept and captures the fundamental flow-density diagram of the CTM explicitly by considering closed-form constraints in the model and thus, eliminates the flow holding-back problem. The proposed solution algorithm is based on the Benders decomposition technique and decomposes the original MINLP to an equivalent Integer Program (IP) (Master problem), and a new MINLP (Primal problem). We will show that the new MINLP has only one optimal non-holding-back solution that can be found by a CTM simulation run. We will prove that the proposed solution technique guarantees convergence to optimal solutions with a finite number of iterations. Furthermore, we propose a dual estimation algorithm for the new MINLP (the Primal problem), which utilizes a simulation-based approach to generate Benders cuts instead of solving a complex optimization program. We applied the proposed solution technique to a simulated network of 20 intersections under various demand patterns and observed an optimality gap of at most 2% under all tested conditions. We compared the solutions of the proposed algorithm with two benchmark algorithms and found reductions in total travel time ranging from 7.0% to 35.7%. [ABSTRACT FROM AUTHOR]

Highlights • Reliable shortest problem with link travel time correlation is studied. • Covariance matrix is decomposed to alleviate the complexity of the problem. • A Lagrangian relaxation solution algorithm is proposed. • Subgradient and deep-cut ellipsoid methods are proposed for updating Lagrangian multipliers. • Large-scale real test results show the algorithm is computationally efficient. Abstract Reliable shortest path (RSP) problem reflects the variability of travel time and is more realistic than standard shortest path problem which considers only the average travel time. This paper describes an algorithm for solving the mean-standard deviation RSP problem considering link travel time correlations. The proposed algorithm adopts the Lagrangian substitution and covariance matrix decomposition technique to deal with the difficulty resulting from non-linearity and non-additivity of the Mixed Integer Non-Linear Program (MINLP). The problem is decomposed into a standard shortest path problem and a convex optimization problem whose optimal solution is proved and the Lagrangian multipliers ranges are related to the eigenvalues of the covariance matrix to further speed up the algorithm. The complexity of the original problem is notably reduced by the proposed algorithm such that it can be scaled to large networks. In addition to the sub-gradient Lagrangian multiplier updating strategy integrated with projection, a novel one based on the deep-cut ellipsoid method is proposed as well. Numerical experiments on large-scale networks show the efficacy of the algorithm in terms of relative duality gap and computational time. Besides, there is evidence showing that, though having longer computational time, the ellipsoid updating method tends to obtain better solutions compared with the sub-gradient method. The algorithm outperforms the existing one-to-one Lagrangian relaxation-based RSP algorithms and the exact Outer Approximation method in the literature. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes a global optimization algorithm for solving a mixed (continuous/discrete) transportation network design problem (MNDP), which is generally expressed as a mathematical programming with equilibrium constraint (MPEC). The upper level of the MNDP aims to optimize the network performance via both expansion of existing links and addition of new candidate links, whereas the lower level is a traditional Wardrop user equilibrium (UE) problem. In this paper, we first formulate the UE condition as a variational inequality (VI) problem, which is defined from a finite number of extreme points of a link-flow feasible region. The MNDP is approximated as a piecewise-linear programming (P-LP) problem, which is then transformed into a mixed-integer linear programming (MILP) problem. A global optimization algorithm based on a cutting constraint method is developed for solving the MILP problem. Numerical examples are given to demonstrate the efficiency of the proposed method and to compare the results with alternative algorithms reported in the literature. [Copyright &y& Elsevier]

Abstract: How to optimally allocate limited freeway sensor resources is of great interest to transportation engineers. In this paper, we focus on the optimal allocation of point sensors, such as loop detectors, to minimize performance measurement errors. Although it has been shown that the minimization problem can be intuitively formulated as a nonlinear program, the formulation is so complex that only heuristic approaches can be used to solve the problem. In this paper, we transform the nonlinear program into an equivalent mixed-integer linear model. The linearized model is shown to have a graphical interpretation and can be solved using resource constrained shortest path algorithms. A customized Branch-and-Bound technique is then proposed to solve the resource constrained shortest path problem. Numerical experiments along an urban freeway corridor demonstrate that this sensor location model is successful in allocating loop detectors to improve the accuracy of travel time estimation. [Copyright &y& Elsevier]

Research highlights • A destination-based model for subloop-based shipping network alteration is proposed. • Optimization problem of port rotation directions is proved to belong to NP-hard class. • The model is transformed to an equivalent mixed-integer linear programming model. • A Benders decomposition method incorporating three acceleration strategies is developed. Abstract Container liner shipping network alteration is a practical manner of shipping network design, which aims to make minor modifications to ameliorate the existing network. In a generic liner shipping network with butterfly ports, each ship route is separated into a set of subloops on the basis of its structure and internal butterfly ports. Reversing the subloop directions has an impact on the network-wide cost including inventory cost, transshipment cost, and slot-purchasing cost. This paper proposes a new destination-based nonlinear model for the subloop-based reversal of port rotation directions with the objective of minimizing the overall network-wide cost. We prove that the addressed problem is NP-hard. Next, the model is transformed to an equivalent mixed-integer linear programming model. Based on the structure of the reformulated model, we develop a Benders decomposition (BD) algorithm and a metaheuristic method to solve practical-size instances. Three acceleration strategies are incorporated into the BD algorithm, which are adding Pareto-optimal cuts, updating big-M coefficients and generating combinatorial Benders cuts. Case studies based on three small examples and an Asia-Europe-Oceania liner shipping network with a total of 46 ports are conducted. Results show that the problem could be efficiently solved by the accelerated BD algorithm and the optimization of subloop directions is conducive to decreasing the network-wide cost especially the inventory cost. [ABSTRACT FROM AUTHOR]

Highlights • An integration of a vehicle routing problem and an infrastructure network restoration crew scheduling problem is proposed. • An initial solution algorithm is proposed to provide an upper bound on the solution. • The integrated problem and initial algorithm are applied to real infrastructure network topologies in Shelby County, TN. Abstract This paper introduces a synchronized routing problem for planning and scheduling restorative efforts for infrastructure networks in the aftermath of a disruptive event. In this problem, a set of restoration crews are dispatched from depots to a road network to restore the disrupted infrastructure network. Two mathematical formulations are presented to scheduling and sequencing disrupted network components to restoration crews and route the crews towards disrupted components to maximize network resilience progress in any given time horizon. In the first formulation, the number of restoration crews assigned to each disrupted component, the arrival time of each assigned crew to each disrupted component and consequently the restoration rate associated with each disrupted component are considered as variables to increase the flexibility of the model in the presence of different disruptive events. Along with the contributions applies in the first formulation, in the second formulation, each disrupted component can be partially active during its restoration process. To find the coordinated routes, we propose a relaxed mixed integer program as well as a set of valid inequalities which relates the planning and scheduling efforts to decision makers policies. The integration of the relaxed formulation and valid inequalities results in a lower bound for the original formulations. We further introduce a feasibility algorithm to derive a strong initial solution for the routing restorative capacity problem. Computational results on gas, water, and electric power infrastructure network instances from Shelby County, TN data, demonstrates both the effectiveness of the proposed model formulation, in solving small to medium scale problems, the strength of the initial solution procedure, especially for large scale problems. [ABSTRACT FROM AUTHOR]

Highlights • A new mathematical formulation is proposed to solve the multiple depot vehicle scheduling problem (MDVSP). • A new decomposition of the formulation is proposed that can be solved using column generation. • Column generation requires less time to solve the new decomposition than to solve the existing set partitioning formulation. • Two new heuristics are proposed that use the new decomposition. • The new heuristics perform better than the existing heuristics in terms of the solution quality and time. Abstract The multiple depot vehicle scheduling problem (MDVSP) with a single vehicle type considers the assignment of timetabled trips to homogeneous vehicles that are stationed at different depots. The assignment of trips to a vehicle also provides a schedule for a vehicle. The objective is to minimise the total cost due to waiting and travelling empty while covering all the trips. In this paper, we propose a new formulation for the MDVSP (termed as the inventory formulation) that uses assignment arcs in a multi-commodity time-space network flow formulation. A general way to solve this multi-commodity network flow problem is to decompose the problem for each commodity (in this case, for each depot). However, we apply Dantzig–Wolfe decomposition to the inventory formulation by decomposing it for each trip. Column generation is used to solve the linear relaxation of the trip-based decomposition. Column generation requires less time to solve the new trip-based decomposition than the existing depot-based decompositions. To obtain a good-quality integer solution to the MDVSP, we propose a solution framework that solves the linear relaxation of the MDVSP iteratively. At each iteration, schedules for certain vehicles in the fleet are finalised. The iterations continue until all the trips receive an allocation. Three different heuristics are proposed based on the solution framework. The computational experiments suggest that the new heuristics provide better quality solutions than the existing heuristics. For instances with a large number of trips, the new heuristics provide solutions in less time than that required by the existing heuristics. [ABSTRACT FROM AUTHOR]

Highlights • We study the TWAVRP with both continuous and discrete sets of time windows and general scenario-based models of uncertainty for several routing-specific parameters. • We propose a novel, decomposition algorithm for the TWAVRP that can be easily parallelized, can utilize any available vehicle routing solver as a black box, and can be readily modified as a heuristic. • We propose a new class of path-based disjunctions for the TWAVRP. • We conduct a comprehensive numerical study demonstrating that our algorithm outperforms all state of the art methods. Abstract We study the strategic decision-making problem of assigning time windows to customers in the context of vehicle routing applications that are affected by operational uncertainty. This problem, known as the Time Window Assignment Vehicle Routing Problem, can be viewed as a two-stage stochastic optimization problem, where time window assignments constitute first-stage decisions, vehicle routes adhering to the assigned time windows constitute second-stage decisions, and the objective is to minimize the expected routing costs. To that end, we develop in this paper a new scenario decomposition algorithm to solve the sampled deterministic equivalent of this stochastic model. From a modeling viewpoint, our approach can accommodate both continuous and discrete sets of feasible time window assignments as well as general scenario-based models of uncertainty for several routing-specific parameters, including customer demands and travel times, among others. From an algorithmic viewpoint, our approach can be easily parallelized, can utilize any available vehicle routing solver as a black box, and can be readily modified as a heuristic for large-scale instances. We perform a comprehensive computational study to demonstrate that our algorithm strongly outperforms all existing solution methods, as well as to quantify the trade-off between computational tractability and expected cost savings when considering a larger number of future scenarios during strategic time window assignment. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies a class of bush-based algorithms (BA) for the user equilibrium (UE) traffic assignment problem, which promise to produce highly precise solutions by exploiting acyclicity of UE flows. Each of the two building blocks of BA, namely the construction of acyclic sub-networks (bush) and the solution of restricted master problems (RMP), is examined and further developed. Four Newton-type algorithms for solving RMP, which can be broadly categorized as route flow and origin flow based, are presented, of which one is newly developed in this paper. Similarities and differences between these algorithms, as well as the relevant implementation issues are discussed in great details. A comprehensive numerical study is conducted using both real and randomly generated networks, which reveals that the relative performance of the algorithms is consistent with the analysis. In particular, the results suggest that swapping flows between shortest and longest route segments consistently outperforms other RMP solution techniques. [Copyright &y& Elsevier]

Abstract: This paper presents a platoon-based traffic signal timing algorithm that reduces traffic delays at major–minor type of intersections. The algorithm reduces traffic delays at intersections by minimizing the interruptions to vehicle platoon movements on the major roads. In this paper, the characteristics of vehicle platoons are discussed, including the key platoon variables and their mathematical distributions. Then the platoon-based traffic signal timing algorithm is illustrated with proposed platoon detector placement and signal control logic. Further, through computer simulations it is shown that the platoon-based algorithm provides better performance at major–minor types of intersections than conventional signal timing algorithms. [Copyright &y& Elsevier]

Abstract: This paper concerns a frequency-based route choice model for congested transit networks, which takes into account the consequences of congestion on the predicted flows as well as on the expected waiting and travel times. The paper builds on the results presented in Correa [Correa, J., 1999. Asignación de flujos de pasajeros en redes de transporte público congestionadas. Engineering thesis, U. de Chile, Santiago] and Cominetti and Correa [Cominetti, R., Correa, J., 2001. Common-lines and passenger assignment in congested transit networks. Transportation Science 35(3), 250–267], extending these to obtain a new characterization of the equilibria which allows us to formulate an equivalent optimization problem in terms of a computable gap function that vanishes at equilibrium. This new model formulation can deal with flow dependent travel times and is a generalization of the previously known strategy (hyperpath) based transit network equilibrium models. The approach leads to an algorithm which has been applied successfully on large scale networks. Computational results for transit networks originating from practice demonstrate the applicability of the proposed approach. [Copyright &y& Elsevier]

Abstract: This paper studies the FIFO property, modelling accuracy and numerical solution of delay-function models, a class of link models widely used in the dynamic user-equilibrium (DUE) traffic assignment problem. It is found that the set of delay functions that can be used in the DUE problem is much smaller than one once expected. In particular, the paper finds that (1) the linear delay function, the only proven FIFO-consistent delay function, substantially overestimates link travel time due to the so-called double-counting effect, (2) the piece-wise linear delay function, an improvement over the linear delay function in reducing double-counting, does not always respect FIFO (i.e., not FIFO-consistent), and (3) a class of smooth, convex delay functions bounded by the linear and piece-wise linear delay functions respects FIFO for certain inflow profiles but not for others. A condition is given to identify those inflow profiles that cause FIFO violations in the delay-function model with nonlinear delay functions. Finally, the paper also provides an accurate and stable solution algorithm for delay-function models. [Copyright &y& Elsevier]

Abstract: This paper deals with algorithms for finding the constrained K-shortest paths (CKSP) and their application to the path enumeration problem. An attractive property of using Constrained Shortest Paths for path enumeration is that paths can be selected based on objective criteria. The conventional way of finding these paths is to compute a sufficiently large number of overall shortest paths, and deleting the ones that do not satisfy the constraints. However for realistically sized networks, combined with restrictive constraints this method becomes unfeasible because of CPU time restrictions. A new method is proposed that finds the feasible shortest paths directly and can be applied in combination with a wide class of constraints. The paper explains how this CKSP algorithm can be implemented using the ordinary shortest path computation as its elementary operation. An example is provided in which the method is used to enumerate paths while avoiding strongly overlapping and overly circuitous paths. In this context the computational performance of the CKSP method is compared with that of the conventional method. On a network consisting of 200 nodes a speed-up factor exceeding 62 has been demonstrated on a problem that involves finding the 200 constrained shortest paths. The speed-up factor increases sharply with the size of the network and the level of restriction of the constraints. As opposed to the conventional method, the proposed implementation of the CKSP method displays only a limited sensitivity to the level of restriction of the constraints. While the conventional method could only deal with small networks, the proposed method can also enumerate paths for more realistically sized networks. [Copyright &y& Elsevier]

This paper considers the second-best problem where not all links of a congested transportation network can be tolled. This paper builds on earlier work, in which the second-best tax rule for this problem was derived for general static networks, so that the solution presented is valid for any graph of the network, and for any set of tolling points available on that network. An algorithm is presented for finding second-best tolls, based on this general solution. A simulation model is used for studying its performance for various archetype pricing schemes: a toll-cordon, area licences, parking policies in the city centre, pricing of a single major highway, and pay-lanes and `free-lanes'' on major highways. Furthermore, an exploratory analysis is given of a method for selecting the optimal location of toll points when not all links can be tolled. [Copyright &y& Elsevier]

This paper examines a three-echelon logistics network in which all supply and transshipment nodes are subject to disruption. We use uncertainty sets to describe the possible scenarios without depending on probabilistic information. We adopt a two-stage robust optimization approach where location decisions are made before and recourse decisions are made after the disruptions are known. We construct three two-stage robust models, which are solved exactly by a column-and-constraint-generation algorithm. Numerical tests demonstrate that the proposed algorithm outperforms the Benders decomposition method in both solution quality and computational time, and that the system’s reliability can be improved with only a slight increase in the normal cost. [ABSTRACT FROM AUTHOR]

Traffic equilibrium models under uncertainty characterize travelers’ route choice behaviors under travel time variability. In this paper, we develop a link -based mean-excess traffic equilibrium (L-METE) model by integrating the sub-additivity property and complete travel time variability characterization of mean-excess travel time (METT), and the computationally tractable additive route cost structure of the conventional user equilibrium (UE) problem. Compared to the majority of relevant models formulated in the route domain, the link -based modeling has two desirable features on modeling flexibility and algorithmic development. First, it avoids the normal route travel time distribution assumption (uniformly imposed for all routes) that inherits from the Central Limit Theorem in most route -based models, permitting the use of any suitable link travel time distributions from empirical studies. Second, the additive route cost structure makes the L-METE model solvable by readily adapting existing UE algorithms without the need of storing/enumerating routes while avoiding the computationally demanding nonadditive shortest path problem and route flow allocations in route-based models, which is a significant benefit for large-scale network applications under uncertainty. [ABSTRACT FROM AUTHOR]