International experience with speed limits during and prior to the energy crisis of 1973–4

This paper presents an artificial neural network (ANN) based method for estimating route travel times between individual locations in an urban traffic network. Fast and accurate estimation of route travel times is required by the vehicle routing and scheduling process involved in many fleet vehicle operation systems such as dial‐a‐ride paratransit, school bus, and private delivery services. The methodology developed in this paper assumes that route travel times are time‐dependent and stochastic and their means and standard deviations need to be estimated. Three feed‐forward neural networks are developed to model the travel time behaviour during different time periods of the day‐the AM peak, the PM peak, and the off‐peak. These models are subsequently trained and tested using data simulated on the road network for the City of Edmonton, Alberta. A comparison of the ANN model with a traditional distance‐based model and a shortest path algorithm is then presented. The practical implication of the ANN method is subsequently demonstrated within a dial‐a‐ride paratransit vehicle routing and scheduling problem. The computational results show that the ANN‐based route travel time estimation model is appropriate, with respect to accuracy and speed, for use in real applications.     

The load-dependent vehicle routing problem and its pick-up and delivery extension

The present paper examines a Vehicle Routing Problem (VRP) of major practical importance which is referred to as the Load-Dependent VRP (LDVRP). LDVRP is applicable for transportation activities where the weight of the transported cargo accounts for a significant part of the vehicle gross weight. Contrary to the basic VRP which calls for the minimization of the distance travelled, the LDVRP objective is aimed at minimizing the total product of the distance travelled and the gross weight carried along this distance. Thus, it is capable of producing sensible routing plans which take into account the variation of the cargo weight along the vehicle trips. The LDVRP objective is closely related to the total energy requirements of the vehicle fleet, making it a credible alternative when the environmental aspects of transportation activities are examined and optimized. A novel LDVRP extension which considers simultaneous pick-up and delivery service is introduced, formulated and solved for the first time. To deal with large-scale instances of the examined problems, we propose a local-search algorithm. Towards an efficient implementation, the local-search algorithm employs a computational scheme which calculates the complex weighted-distance objective changes in constant time. Solution results are presented for both problems on a variety of well-known test cases demonstrating the effectiveness of the proposed solution approach. The structure of the obtained LDVRP and VRP solutions is compared in pursuit of interesting conclusions on the relative suitability of the two routing models, when the decision maker must deal with the weighted distance objective. In addition, results of a branch-and-cut procedure for small-scale instances of the LDVRP with simultaneous pick-ups and deliveries are reported. Finally, extensive computational experiments have been performed to explore the managerial implications of three key problem characteristics, namely the deviation of customer demands, the cargo to tare weight ratio, as well as the size of the available vehicle fleet.     

A stochastic multimodal reliable network design problem under adverse weather conditions

This paper formulates a network design problem (NDP) for finding the optimal public transport service frequencies and link capacity expansions in a multimodal network with consideration of impacts from adverse weather conditions. The proposed NDP aims to minimize the sum of expected total travel time, operational cost of transit services, and construction cost of link capacity expansions under an acceptable level of variance of total travel time. Auto, transit, bus, and walking modes are considered in the multimodal network model for finding the equilibrium flows and travel times. In the proposed network model, demands are assumed to follow Poisson distribution, and weather‐dependent link travel time functions are adopted. A probit‐based stochastic user equilibrium, which is based on the perceived expected travel disutility, is used to determine the multimodal route of the travelers. This model also considers the strategic behavior of the public transport travelers in choosing their routes, that is, common‐line network. Based on the stochastic multimodal model, the mean and variance of total travel time are analytical estimated for setting up the NDP. A sensitivity‐based solution algorithm is proposed for solving the NDP, and two numerical examples are adopted to demonstrate the characteristics of the proposed model. Copyright © 2014 John Wiley & Sons, Ltd.     

Ferry service network design: optimal fleet size,routing, and scheduling

The study formulated a ferry network design problem by considering the optimal fleet size, routing, and scheduling for both direct and multi-stop services. The objective function combines both the operator and passengers’ performance measures. Mathematically, the model is formulated as a mixed integer multiple origin–destination network flow problem with ferry capacity constraints. To solve this problem of practical size, this study developed a heuristic algorithm that exploits the polynomial-time performance of shortest path algorithms. Two scenarios of ferry services in Hong Kong were solved to demonstrate the performance of the heuristic algorithm. The results showed that the heuristic produced solutions that were within 1.3% from the CPLEX optimal solutions. The computational time is within tens of seconds even for problem size that is beyond the capability of CPLEX.     

An integrated modelling approach for the bicriterion vehicle routing and scheduling problem with environmental considerations

The consideration of pollution in routing decisions gives rise to a new routing framework where measures of the environmental implications are traded off with business performance measures. To address this type of routing decisions, we formulate and solve a bi-objective time, load and path-dependent vehicle routing problem with time windows (BTL-VRPTW). The proposed formulation incorporates a travel time model representing realistically time varying traffic conditions. A key feature of the problem under consideration is the need to address simultaneously routing and path finding decisions. To cope with the computational burden arising from this property of the problem we propose a network reduction approach. Computational tests on the effect of the network reduction approach on determining non-dominated solutions are reported. A generic solution framework is proposed to address the BTL-VRPTW. The proposed framework combines any technique that creates capacity-feasible routes with a routing and scheduling method that aims to convert the identified routes to problem solutions. We show that transforming a set of routes to BTL-VRPTW solutions is equivalent to solving a bi-objective time dependent shortest path problem on a specially structured graph. We propose a backward label setting technique to solve the emerging problem that takes advantage of the special structure of the graph. The proposed generic solution framework is implemented by integrating the routing and scheduling method into an Ant Colony System algorithm. The accuracy of the proposed algorithm was assessed on the basis of its capability to determine minimum travel time and fuel consumption solutions. Although the computational results are encouraging, there is ample room for future research in algorithmic advances on addressing the proposed problem.     

Distributed coordinated in-vehicle online routing using mixed-strategy congestion game

This study proposes a coordinated online in-vehicle routing mechanism for smart vehicles with real-time information exchange and portable computation capabilities. The proposed coordinated routing mechanism incorporates a discrete choice model to account for drivers’ behavior, and is implemented by a simultaneously-updating distributed algorithm. This study shows the existence of an equilibrium coordinated routing decision for the mixed-strategy routing game and the convergence of the distributed algorithm to the equilibrium routing decision, assuming individual smart vehicles are selfish players seeking to minimize their own travel time. Numerical experiments conducted based on Sioux Falls city network indicate that the proposed distributed algorithm converges quickly under different smart vehicle penetrations, thus it possesses a great potential for online applications. Moreover, the proposed coordinated routing mechanism outperforms traditional independent selfish-routing mechanism; it reduces travel time for both overall system and individual vehicles, which represents the core idea of Intelligent Transportation Systems (ITS).     

A rolling horizon algorithm for auto-carrier transportation

This paper introduces a rolling horizon algorithm to plan the delivery of vehicles to automotive dealers by a heterogeneous fleet of auto-carriers. The problem consists in scheduling the deliveries over a multiple-day planning horizon during which requests for transportation arrive dynamically. In addition, the routing of the auto-carriers must take into account constraints related to the loading of the vehicles on the carriers. The objective is to minimize the sum of traveled distances, fixed costs for auto-carrier operation, service costs, and penalties for late deliveries. The problem is solved by a heuristic that first selects the vehicles to be delivered in the next few days and then optimizes the deliveries by an iterated local search procedure. A branch-and-bound search is used to check the feasibility of the loading. To handle the dynamic nature of the problem, the complete algorithm is applied repeatedly in a rolling horizon framework. Computational results on data from a major European logistics service provider show that the heuristic is fast and yields significant improvements compared to the sequential solution of independent daily problems.     

Predicting travel time reliability using mobile phone GPS data

Estimates of road speeds have become commonplace and central to route planning, but few systems in production provide information about the reliability of the prediction. Probabilistic forecasts of travel time capture reliability and can be used for risk-averse routing, for reporting travel time reliability to a user, or as a component of fleet vehicle decision-support systems. Many of these uses (such as those for mapping services like Bing or Google Maps) require predictions for routes in the road network, at arbitrary times; the highest-volume source of data for this purpose is GPS data from mobile phones. We introduce a method (TRIP) to predict the probability distribution of travel time on an arbitrary route in a road network at an arbitrary time, using GPS data from mobile phones or other probe vehicles. TRIP captures weekly cycles in congestion levels, gives informed predictions for parts of the road network with little data, and is computationally efficient, even for very large road networks and datasets. We apply TRIP to predict travel time on the road network of the Seattle metropolitan region, based on large volumes of GPS data from Windows phones. TRIP provides improved interval predictions (forecast ranges for travel time) relative to Microsoft’s engine for travel time prediction as used in Bing Maps. It also provides deterministic predictions that are as accurate as Bing Maps predictions, despite using fewer explanatory variables, and differing from the observed travel times by only 10.1% on average over 35,190 test trips. To our knowledge TRIP is the first method to provide accurate predictions of travel time reliability for complete, large-scale road networks.     

Multi-objective optimization of train routing problem combined with train scheduling on a high-speed railway network

Based on train scheduling, this paper puts forward a multi-objective optimization model for train routing on high-speed railway network, which can offer an important reference for train plan to provide a better service. The model does not only consider the average travel time of trains, but also take the energy consumption and the user satisfaction into account. Based on this model, an improved GA is designed to solve the train routing problem. The simulation results demonstrate that the accurate algorithm is suitable for a small-scale network, while the improved genetic algorithm based on train control (GATC) applies to a large-scale network. Finally, a sensitivity analysis of the parameters is performed to obtain the ideal parameters; a perturbation analysis shows that the proposed method can quickly handle the train disturbance.     

A stochastic fleet size and mix model for maintenance operations at offshore wind farms

A fleet of vessels and helicopters is needed to support maintenance operations at offshore wind farms. The cost of this fleet constitutes a major part of the total maintenance costs, hence keeping an optimal or near-optimal fleet is essential to reduce the cost of energy. In this paper we study the vessel fleet size and mix problem that arises for the maintenance operations at offshore wind farms, and propose a stochastic three-stage programming model. The stochastic model considers uncertainty in vessel spot rates, weather conditions, electricity prices and failures to the system. The model is tested on realistic-sized problem instances, and the results show that it is valuable to consider uncertainty and that the proposed model can be used to solve instances of a realistic size.     

Optimal speed detector density for the network with travel time information

In the expressway network, detectors are installed on the links for detecting the travel time information while the predicted travel time can be provided by the route guidance system (RGS). The speed detector density can be determined to influence flow distributions in such a way that the precision of the travel time information and the social cost of the speed detectors are optimized, provided that each driver chooses the minimum perceived travel time path in response to the predicted travel time information. In this paper, a bilevel programming model is proposed for the network with travel time information provided by the RGS. The lower-level problem is a probit-based traffic assignment model, while the upper-level problem is to determine the speed detector density that minimizes the measured travel time error variance as well as the social cost of the speed detectors. The sensitivity analysis based algorithm is proposed for the bilevel programming problem. Numerical examples are provided to illustrate the applications of the proposed model and of the solution algorithm.     

带时间窗的混和车辆路径问题的优化算法研究

文章针对带时间窗约束的混合车辆路径问题的特点,建立了带时间窗的混合车辆路径问题的数学模型,并设计了变邻域禁忌搜索算法对该问题进行求解。通过标准算例测试及与现有文献计算结果的比较,验证了该算法的有效性。     

A joint optimization model for liner container cargo assignment problem using state-augmented shipping network framework

This paper proposes a state-augmented shipping (SAS) network framework to integrate various activities in liner container shipping chain, including container loading/unloading, transshipment, dwelling at visited ports, in-transit waiting and in-sea transport process. Based on the SAS network framework, we develop a chance-constrained optimization model for a joint cargo assignment problem. The model attempts to maximize the carrier’s profit by simultaneously determining optimal ship fleet capacity setting, ship route schedules and cargo allocation scheme. With a few disparities from previous studies, we take into account two differentiated container demands: deterministic contracted basis demand received from large manufacturers and uncertain spot demand collected from the spot market. The economies of scale of ship size are incorporated to examine the scaling effect of ship capacity setting in the cargo assignment problem. Meanwhile, the schedule coordination strategy is introduced to measure the in-transit waiting time and resultant storage cost. Through two numerical studies, it is demonstrated that the proposed chance-constrained joint optimization model can characterize the impact of carrier’s risk preference on decisions of the container cargo assignment. Moreover, considering the scaling effect of large ships can alleviate the concern of cargo overload rejection and consequently help carriers make more promising ship deployment schemes.     

Solving the station-based one-way carsharing network planning problem with relocations and non-linear demand

One-way station-based carsharing systems allow users to return a rented car to any designated station, which could be different from the origin station. Existing research has been mainly focused on the vehicle relocation problem to deal with the travel demand fluctuation over time and demand imbalance in space. However, the strategic planning of the stations’ location and their capacity for one-way carsharing systems has not been well studied yet, especially when considering vehicle relocations simultaneously. This paper presents a Mixed-integer Non-linear Programming (MINLP) model to solve the carsharing station location and capacity problem with vehicle relocations. This entails considering several important components which are for the first time integrated in the same model. Firstly, relocation operations and corresponding relocation costs are taken into consideration to address the imbalance between trip requests and vehicle availability. Secondly, the flexible travel demand at various time steps is taken as the input to the model avoiding deterministic requests. Thirdly, a logit model is constructed to represent the non-linear demand rate by using the ratio of carsharing utility and private car utility. To solve the MINLP model, a customized gradient algorithm is proposed. The application to the SIP network in Suzhou, China, demonstrates that the algorithm can solve a real world large scale problem in reasonable time. The results identify the pricing and parking space rental costs as the key factors influencing the profitability of carsharing operators. Also, the carsharing station location and fleet size impact the vehicle relocation and carsharing patronage.     

A new schedule-based transit assignment model with travel strategies and supply uncertainties

This paper proposes a new scheduled-based transit assignment model. Unlike other schedule-based models in the literature, we consider supply uncertainties and assume that users adopt strategies to travel from their origins to their destinations. We present an analytical formulation to ensure that on-board passengers continuing to the next stop have priority and waiting passengers are loaded on a first-come-first-serve basis. We propose an analytical model that captures the stochastic nature of the transit schedules and in-vehicle travel times due to road conditions, incidents, or adverse weather. We adopt a mean variance approach that can consider the covariance of travel time between links in a space–time graph but still lead to a robust transit network loading procedure when optimal strategies are adopted. The proposed model is formulated as a user equilibrium problem and solved by an MSA-type algorithm. Numerical results are reported to show the effects of supply uncertainties on the travel strategies and departure times of passengers.     

Solution methods for the taxi pooling problem

In Taiwan, taxi pooling is currently performed by some taxi companies using a trial-and-error experience-based method, which is neither effective nor efficient. There is, however, little in the literature on effective models and solution methods for solving the taxi pooling problem. Thus, in this study we employ network flow techniques and a mathematical programming method to develop a taxi pooling solution method. This method is composed of three models. First, a fleet routing/scheduling model is constructed to produce fleet/passenger routes and schedules. A solution algorithm, based on Lagrangian relaxation, a sub-gradient method and a heuristic to find the upper bound of the solution, is proposed to solve the fleet routing/scheduling model. Then, two single taxi-passenger matching models are constructed with the goals of decreasing number of passenger transfers and matching all passengers and taxis. These two taxi-passenger matching models are directly solved using a mathematical programming solver. For comparison with the solution method, we also develop another heuristic by modifying a heuristic recently proposed for solving a one-to-many taxi pooling problem. The performance of the solution method and the additional heuristic are evaluated by carrying out a case study using real data and suitable assumptions. The test results show that these two solution methods could be useful in practice.     

Eco-routing problem considering fuel consumption and probabilistic travel time budget

Road transportation is one of the major sources of greenhouse gas emissions. To reduce energy consumption and alleviate this environmental problem, this study aims to develop an eco-routing algorithm for navigation systems. Considering that both fuel consumption and travel time are important factors when planning a trip, the proposed routing algorithm finds a path that consumes the minimum amount of gasoline while ensuring that the travel time satisfies a specified travel time budget and an on-time arrival probability. We first develop link-based fuel consumption models based on vehicle dynamics, and then the Lagrangian-relaxation-based heuristic approach is proposed to efficiently solve this NP-hard problem. The performance of the proposed eco-routing strategy is verified in a large-scale network with real travel time and fuel consumption data. Specifically, a sensitivity analysis of fuel consumption reduction for travel demand and travel time buffer is discussed in our simulation study.     

Energy impact evaluation for eco-routing and charging of autonomous electric vehicle fleet: Ambient temperature consideration

This paper studies the heterogeneous energy cost and charging demand impact of autonomous electric vehicle (EV) fleet under different ambient temperature. A data-driven method is introduced to formulate a two-dimensional grid stochastic energy consumption model for electric vehicles. The energy consumption model aids in analyzing EV energy cost and describing uncertainties under variable average vehicle trip speed and ambient temperature conditions. An integrated eco-routing and optimal charging decision making framework is designed to improve the capability of autonomous EV’s trip level energy management in a shared fleet. The decision making process helps to find minimum energy cost routes with consideration of charging strategies and travel time requirements. By taking advantage of derived models and technologies, comprehensive case studies are performed on a data-driven simulated transportation network in New York City. Detailed results show us the heterogeneous energy impact and charging demand under different ambient temperature. By giving the same travel demand and charging station information, under the low and high ambient temperature within each month, there exist more than 20% difference of overall energy cost and 60% difference of charging demand. All studies will help to construct sustainable infrastructure for autonomous EV fleet trip level energy management in real world applications.     

Eco-system optimal time-dependent flow assignment in a congested network

This research addresses the eco-system optimal dynamic traffic assignment (ESODTA) problem which aims to find system optimal eco-routing or green routing flows that minimize total vehicular emission in a congested network. We propose a generic agent-based ESODTA model and a simplified queueing model (SQM) that is able to clearly distinguish vehicles’ speed in free-flow and congested conditions for multi-scale emission analysis, and facilitates analyzing the relationship between link emission and delay. Based on the SQM, an expanded space-time network is constructed to formulate the ESODTA with constant bottleneck discharge capacities. The resulting integer linear model of the ESODTA is solved by a Lagrangian relaxation-based algorithm. For the simulation-based ESODTA, we present the column-generation-based heuristic, which requires link and path marginal emissions in the embedded time-dependent least-cost path algorithm and the gradient-projection-based descent direction method. We derive a formula of marginal emission which encompasses the marginal travel time as a special case, and develop an algorithm for evaluating path marginal emissions in a congested network. Numerical experiments are conducted to demonstrate that the proposed algorithm is able to effectively obtain coordinated route flows that minimize the system-wide vehicular emission for large-scale networks.     

Does regional travel time unreliability influence mode choice?

Researchers and practitioners highlight the unreliability of travel as a potential weak link in the transportation system which may inhibit individuals’ accessibility and urban economic activity. With the trend towards increasing traffic congestion, the outlook suggests that travel conditions will become structurally less reliable over time, but that not all places will be equally affected. But is travel time unreliability a problem? This study uses global positioning systems travel survey data for Chicago to build a regional model of travel time unreliability. The results suggest that unreliability varies spatially during different time periods, but that the average overall network unreliability varies little across times in the day. Using the Chicago Metropolitan Agency for Planning (CMAP)’s 2007 Travel Tracker Survey, a household travel diary survey including both GPS and non-GPS components, we estimate a mode choice model for work trips to explore the influence of unreliability on travel behavior. The results suggest that unreliable auto travel conditions induce mode switching to transit and that the influence is strongest when service by train is already faster than by car. This further suggests that auto travel unreliability may have the strongest influence in metropolitan regions with highly-competitive transit systems. Nevertheless, the influence of travel unreliability is limited and is not the underlying driver of travel decision-making.