Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm

This paper addresses a Time Dependent Capacitated Vehicle Routing Problem with stochastic vehicle speeds and environmental concerns. The problem has been formulated as a Markovian Decision Process. As distinct from the traditional attempts on the problem, while estimating the amount of fuel consumption and emissions, the model takes time-dependency and stochasticity of the vehicle speeds into account. The Time Dependent Capacitated Vehicle Routing Problem is known to be NP-Hard for even deterministic settings. Incorporating uncertainty to the problem increases complexity, which renders classical optimization methods infeasible. Therefore, we propose an Approximate Dynamic Programming based heuristic as a decision aid tool for the problem. The proposed Markovian Decision Model and Approximate Dynamic Programming based heuristic are flexible in terms that more environmentally friendly solutions can be obtained by changing the objective function from cost minimization to emissions minimization. The added values of the proposed decision support tools have been shown through computational analyses on several instances. The computational analyses show that incorporating vehicle speed stochasticity into decision support models has potential to improve the performance of resulting routes in terms of travel duration, emissions and travel cost. In addition, the proposed heuristic provides promising results within relatively short computation times.     

The Hybrid Vehicle Routing Problem

In this paper the Hybrid Vehicle Routing Problem (HVRP) is introduced and formalized. This problem is an extension of the classical VRP in which vehicles can work both electrically and with traditional fuel. The vehicle may change propulsion mode at any point of time. The unitary travel cost is much lower for distances covered in the electric mode. An electric battery has a limited capacity and may be recharged at a recharging station (RS). A limited number of RS are available. Once a battery has been completely discharged, the vehicle automatically shifts to traditional fuel propulsion mode. Furthermore, a maximum route duration is imposed according to contracts regulations established with the driver. In this paper, a Mixed Integer Linear Programming formulation is presented and a Large Neighborhood Search based Matheuristic is proposed. The algorithm starts from a feasible solution and consists into destroying, at each iteration, a small number of routes, letting unvaried the other ones, and reconstructing a new feasible solution running the model on only the subset of customers involved in the destroyed routes. This procedure allows to completely explore a large neighborhood within very short computational time. Computational tests that show the performance of the matheuristic are presented. The method has also been tested on a simplified version of the HVRP already presented in the literature, the Green Vehicle Routing Problem (GVRP), and competitive results have been obtained.     

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.     

Vehicle routing problem and driver behaviour: a review and framework for analysis

Vehicle routing problems (VRPs) whose typical objective is to minimise total travel costs over a tour have evolved over the years with objectives ranging from minimising travel times and distances to minimising pollution and fuel consumption. However, driver behaviour continues to be neglected while planning for vehicle routes. Factors such as traffic congestion levels, monotonous drives and fatigue have an impact on the behaviour of drivers, which in turn might affect their speed-choice and route-choice behaviours. The behaviour of drivers and their subsequent decision-making owing to these factors impact the revenue of transport companies and could lead to huge losses in extreme cases. There have been studies on the behaviour of drivers in isolation, without inclusion of the objectives and constraints of the traditional routing problem. This paper presents a review of existing models of VRP, planner behaviour models in the VRP context and driver behaviour models and provides a motivation to integrate these models in a stochastic traffic environment to produce practical, economic and driver-friendly logistics solutions. The paper provides valuable insights on the relevance of behavioural issues in logistics and highlights the modelling implications of incorporating planner and driver behaviour in the framework of routing problems.     

Use of hybrid vehicles in Japan: An analysis of used car market data

Despite the rapid market penetration of hybrid vehicles (HVs), their usage and contributions to environmental protection have not been examined by vehicle traveling data. In this paper, we analyzed Japan’s used car market data to understand how HVs are used on the street. We find GV drivers with high travel demand switched from GVs to HVs during the transition period. Despite HV owners driving much longer distances than conventional gasoline vehicle (GV) owners, they emit less carbon dioxide (CO₂) emissions, owing to better fuel economy. We also find that HV owners spend roughly the same amount of money annually as GV owners. However, the per-kilometer travel cost of HVs is much lower than that of GVs even if the depreciation cost of the vehicle and vehicle related taxes are included in the analysis.     

Linking land use with household vehicle emissions in the central puget sound: methodological framework and findings

A leading cause of air pollution in many urban regions is mobile source emissions that are largely attributable to household vehicle travel. While household travel patterns have been previously related with land use in the literature (Crane, R., 1996. Journal of the American Planning Association 62 (1, Winter); Cervero, R. and Kockelman, C., 1997. Transportation Research Part D 2 (3), 199–219), little work has been conducted that effectively extends this relationship to vehicle emissions. This paper describes a methodology for quantifying relationships between land use, travel choices, and vehicle emissions within the Seattle, Washington region. Our analysis incorporates land use measures of density and mix which affect the proximity of trip origins to destinations; a measure of connectivity which impacts the directness and completeness of pedestrian and motorized linkages; vehicle trip generation by operating mode; vehicle miles/h of travel and speed; and estimated household vehicle emissions of nitrogen oxides, volatile organic compounds, and carbon monoxide. The data used for this project consists of the Puget Sound Transportation Panel Travel Survey, the 1990 US Census, employment density data from the Washington State Employment Security Office, and information on Seattle’s vehicle fleet mix and climatological attributes provided by the Washington State Department of Ecology. Analyses are based on a cross-sectional research design in which comparisons are made of variations in household travel demand and emissions across alternative urban form typologies. Base emission rates from MOBILE5a and separate engine start rates are used to calculate total vehicle emissions in grams accounting for fleet characteristics and other inputs reflecting adopted transportation control measures. Emissions per trip are based on the network distance of each trip, average travel speed, and a multi-stage engine operating mode (cold start, hot start, and stabilized) function.     

Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times

This paper presents a dynamic vehicle routing and scheduling model that incorporates real time information using variable travel times. Dynamic traffic simulation was used to update travel times. The model was applied to a test road network. Results indicated that the total cost decreased by implementing the dynamic vehicle routing and scheduling model with the real time information based on variable travel times compared with that of the forecast model. As well, in many cases total running times of vehicles were also decreased. Therefore, the dynamic vehicle routing and scheduling model will be beneficial for both carriers in reducing total costs and society at large by alleviating traffic congestion.     

Distance and time in intermodal goods transport networks in Europe: A generic approach

This paper is about distance and time as factors of competitiveness of intermodal transport. It reviews the relevance of the factors, evaluates time models in practice, compares network distances and times in alternative bundling networks with geometrically varied layouts, and points out how these networks perform in terms of vehicle scale, frequency and door-to-door time. The analysis focuses on intermodal transport in Europe, especially intermodal rail transport, but is in search for generic conclusions. The paper does not incorporate the distance and time results in cost models, and draws conclusions for transport innovation, wherever this is possible without cost modelling. For instance, the feature vehicle scale, an important factor of transport costs, is analysed and discussed.Distance and time are important factors of competitiveness of intermodal transport. They generate (direct) vehicle costs and – via transport quality – indirect costs to the customers. Clearly direct costs/prices are the most important performance of the intermodal transport system. The relevance of quality performances is less clarified. Customers emphasise the importance of a good match between the transport and the logistic system. In this framework (time) reliability is valued high. Often transport time, arrival and departure times, and frequency have a lower priority. But such conclusions can hardy be generalised. The range of valuations reflects the heterogeneity of situations. Some lack of clarity is obviously due to overlapping definitions of different performance types.The following parts of the paper are about two central fields of network design, which have a large impact on transport costs and quality, namely the design of vehicle roundtrips (and acceleration of transport speed) and the choice of bundling type: do vehicles provide direct services or run in what we call complex bundling networks? An example is the hub-and-spoke network. The objective of complex bundling is to increase vehicle scale and/or transport frequency even if network volumes are restricted. Complex bundling requires intermediate nodes for the exchange of load units. Examples of complex bundling networks are the hub-and-spoke network or the line network.Roundtrip and bundling design are interrelated policy fields: an acceleration of the roundtrip speed, often desirable from the cost point of view, can often only be carried out customer friendly, if the transport frequency is increased. But often the flow size is not sufficient for a higher frequency. Then a change of bundling model can be an outcome.Complex bundling networks are known to have longer average distances and times, the latter also due to the presence of additional intermediate exchange nodes. However, this disadvantage is – inside the limits of maximal vehicle sizes – overruled by the advantage of a restricted number of network links. Therefore generally, complex bundling networks have shorter total vehicle distances and times. This expression of economies of scale implies lower vehicle costs per load unit.The last part of the paper presents door-to-door times of load units of complex bundling networks and compares them with unimodal road transport. The times of complex bundling networks are larger than that of networks with direct connections, but nevertheless competitive with unimodal road transport, except for short distances.     

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.     

Routing aspects of electric vehicle drivers and their effects on network performance

This study investigates the routing aspects of battery electric vehicle (BEV) drivers and their effects on the overall traffic network performance. BEVs have unique characteristics such as range limitation, long battery recharging time, and recuperation of energy lost during the deceleration phase if equipped with regenerative braking system (RBS). In addition, the energy consumption rate per unit distance traveled is lower at moderate speed than at higher speed. This raises two interesting questions: (i) whether these characteristics of BEVs will lead to different route selection compared to conventional internal combustion engine vehicles (ICEVs), and (ii) whether such route selection implications of BEVs will affect the network performance. With the increasing market penetration of BEVs, these questions are becoming more important. This study formulates a multi-class dynamic user equilibrium (MCDUE) model to determine the equilibrium flows for mixed traffic consisting of BEVs and ICEVs. A simulation-based solution procedure is proposed for the MCDUE model. In the MCDUE model, BEVs select routes to minimize the generalized cost which includes route travel time, energy related costs and range anxiety cost, and ICEVs to minimize route travel time. Results from numerical experiments illustrate that BEV drivers select routes with lower speed to conserve and recuperate battery energy while ICEV drivers select shortest travel time routes. They also illustrate that the differences in route choice behavior of BEV and ICEV drivers can synergistically lead to reduction in total travel time and the network performance towards system optimum under certain conditions.     

A real-life Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet: Formulation and Adaptive Large Neighborhood Search based Matheuristic

In this paper, a new rich Vehicle Routing Problem that could arise in a real life context is introduced and formalized: the Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet. The goal of the problem is to minimize the total delivery cost. A heterogeneous fleet composed of vehicles with different capacity, characteristics (i.e. refrigerated vehicles) and hourly costs is considered. A limit on the maximum route duration is imposed. Unlike what happens in classical multi-depot VRP, not every customer may/will be served by all the vehicles or from all the depots. The planning horizon, as in most real life applications, consists of multiple periods, and the period in which each route is performed is a variable of the problem. The set of periods, within the time horizon, in which the delivery may be carried out is known for each customer. A Mixed Integer Programming (MIP) formulation for MDMPVRPHF is presented in this paper, and an Adaptive Large Neighborhood Search (ALNS) based Matheuristic approach is proposed, in which different destroy operators are defined. Computational results, pertaining to realistic instances, which show the effectiveness of the proposed method, are provided.     

The corridor problem: Preliminary results on the no-toll equilibrium

Consider a traffic corridor that connects a continuum of residential locations to a point central business district, and that is subject to flow congestion. The population density function along the corridor is exogenous, and except for location vehicles are identical. All vehicles travel along the corridor from home to work in the morning rush hour, and have the same work start-time but may arrive early. The two components of costs are travel time costs and schedule delay (time early) costs. Determining equilibrium and optimum traffic flow patterns for this continuous model, and possible extensions, is termed “The Corridor Problem”. Equilibria must satisfy the trip-timing condition, that at each location no vehicle can experience a lower trip price by departing at a different time. This paper investigates the no-toll equilibrium of the basic Corridor Problem.     

Solving the User Optimum Privately Owned Automated Vehicles Assignment Problem (UO-POAVAP): A model to explore the impacts of self-driving vehicles on urban mobility

Interest in vehicle automation has been growing in recent years, especially with the very visible Google car project. Although full automation is not yet a reality there has been significant research on the impacts of self-driving vehicles on traffic flows, mainly on interurban roads. However, little attention has been given to what could happen to urban mobility when all vehicles are automated. In this paper we propose a new method to study how replacing privately owned conventional vehicles with automated ones affects traffic delays and parking demand in a city. The model solves what we designate as the User Optimum Privately Owned Automated Vehicles Assignment Problem (UO-POAVAP), which dynamically assigns family trips in their automated vehicles in an urban road network from a user equilibrium perspective where, in equilibrium, households with similar trips should have similar transport costs. Automation allows a vehicle to travel without passengers to satisfy multiple household trips and, if needed, to park itself in any of the network nodes to benefit from lower parking charges. Nonetheless, the empty trips can also represent added congestion in the network. The model was applied to a case study based on the city of Delft, the Netherlands. Several experiments were done, comparing scenarios where parking policies and value of travel time (VTT) are changed. The model shows good equilibrium convergence with a small difference between the general costs of traveling for similar families. We were able to conclude that vehicle automation reduces generalized transport costs, satisfies more trips by car and is associated with increased traffic congestion because empty vehicles have to be relocated. It is possible for a city to charge for all street parking and create free central parking lots that will keep total transport costs the same, or reduce them. However, this will add to congestion as traffic competes to access those central nodes. In a scenario where a lower VTT is experienced by the travelers, because of the added comfort of vehicle automation, the car mode share increases. Nevertheless this may help to reduce traffic congestion because some vehicles will reroute to satisfy trips which previously were not cost efficient to be done by car. Placing the free parking in the outskirts is less attractive due to the extra kilometers but with a lower VTT the same private vehicle demand would be attended with the advantage of freeing space in the city center.     

A disjunctive convex programming approach to the pollution-routing problem

The pollution-routing problem (PRP) aims to determine a set of routes and speed over each leg of the routes simultaneously to minimize the total operational and environmental costs. A common approach to solve the PRP exactly is through speed discretization, i.e., assuming that speed over each arc is chosen from a prescribed set of values. In this paper, we keep speed as a continuous decision variable within an interval and propose new formulations for the PRP. In particular, we build two mixed-integer convex optimization models for the PRP, by employing tools from disjunctive convex programming. These are the first arc-based formulations for the PRP with continuous speed. We also derive several families of valid inequalities to further strengthen both models. We test the proposed formulations on benchmark instances. Some instances are solved to optimality for the first time.     

Trial and error method for optimal tradable credit schemes: The network case

Recent studies on the new congestion reduction method―tradable credit scheme rely on the full information of speed‐flow relationship, demand function, and generalized cost. As analytical travel demand, functions are difficult to establish in practice. This paper develops a trial and error method for selecting optimal credit schemes for general networks in the absence of demand functions. After each trial of tradable credit scheme, the credit charging scheme and total amount of credits to be distributed are updated by both observed link flows at traffic equilibrium and revealed credit price at market equilibrium. The updating strategy is based on the method of successive averages and its convergence is established theoretically. Our numerical experiments demonstrate that the method of successive averages based trial and error method for tradable credit schemes has a lower convergence speed in comparison with its counterpart for congestion pricing and could be enhanced by exploring more efficient methods that make full use of credit price information. Copyright © 2013 John Wiley & Sons, Ltd.     

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.     

Assessing carbon reduction effects toward the mode shift of green transportation system

Plans are underway to introduce green transportation systems at Taiwan's famous scenic spot, Sun Moon Lake, to reduce carbon emissions. Carbon reduction effects after changing the current lake tour modes are assessed using a nested logit model with a stated preference survey, which investigated tourists' choice preferences. The empirical results reveal that the modes of electric bus, electric vehicle sharing, and bike are clustered in the same competitive group. Travel cost, in‐vehicle travel time, and out‐vehicle travel time are found to be statistically significant with the expected negative effects. In particular, the attribute of carbon reduction is only significant for green tourists, who are willing to pay US$ 3.5/kg of carbon saved. The result indicates that more efficient carbon reduction is possible by restricting the usage of gasoline vehicles rather than improving the service levels of low‐carbon modes. Notably, the effect of parking charges on emission reduction is equal to the amount of carbon dioxide absorbed by 4511 trees per day. Copyright © 2016 John Wiley & Sons, Ltd.     

Can using global positioning system (GPS) improve trip reporting?

In the United States, information about daily travel patterns is generally captured using self-reported information using a written diary and telephone retrieval (or mail-back of diary forms). Problems with these methods include lack of reporting for short trips, poor data quality on travel start and end times, total trip times and destination locations.This project combined a hand-held computer (Personal Digital Assistant or PDA) with a Global Positioning System (GPS) receiver to capture vehicle-based, daily travel information. The vehicle driver uses a menu to enter variables such as trip purpose and vehicle occupancy, but other data such as date, start time, end time, and vehicle position (latitude and longitude) are collected automatically at frequent intervals. The field test was conducted in Lexington, Kentucky in fall, 1996, with 100 households to use the equipment for six days. Respondents also completed a telephone survey for one day of travel (attempted for day 5).The field test was a test of equipment and willingness of the general public to participate, rather than to obtain a statistically valid travel behavior dataset for the Lexington area. One improvement to the hardware would be for the equipment to turn on automatically. There are limitations to the dataset and analyses that are discussed where appropriate. Although the dataset is small, this paper compares the results of the machine-recorded trips to self-reported trips captured by telephone interview.Self-reported distances are much longer than distances recorded by the PDA/GPS. A recalled distance of 10 miles was, on average, only 6.5 miles when the GPS points are matched to a positionally accurate base file. Similarly, recalled times generally exceed median measured values, but the differences are much smaller than for distances. Respondents reported that data entry of 1 min at the beginning of each trip over the six-day survey period was not burdensome.Recommendations for improving the hardware and software for conducting other travel surveys using GPS, and improving the utility of travel data collected using GPS are provided. One of the benefits of incorporating a GPS device into the survey process was the ability to collect information on route choice and travel speed. However, this paper does not address these topics.     

Estimating vehicle speed with embedded inertial sensors

Pavements were instrumented with inertial sensors, and the possibility of estimating the speed of a passing vehicle was investigated numerically and experimentally from the measurements of two embedded accelerometers. The sensors were spaced apart in the travel direction, and subsequently the speed was directly related to the time delay between the received signals. No assumption was made regarding the vehicle and pavement properties. Model accelerations were presented, studied, and contrasted against field measurements; the latter were shown to be dominated by random vibration sources. Two calculation techniques were offered and applied to handle the noisy data. The first was based on time-centroids, and the second was based on cross-correlation with kernel presmoothing. The overall concept is deemed promising not only for inferring speeds but also for extracting additional traffic characteristics such as axle spacing and relative axle load distributions.     

Dynamic operations and pricing of electric unmanned aerial vehicle systems and power networks

The emergence of electric unmanned aerial vehicle (E-UAV) technologies, albeit somewhat futuristic, is anticipated to pose similar challenges to the system operation as those of electric vehicles (EVs). Notably, the charging of EVs en-route at charging stations has been recognized as a significant type of flexible load for power systems, which often imposes non-negligible impacts on the power system operator’s decisions on electricity prices. Meanwhile, the charging cost based on charging time and price is part of the trip cost for the users, which can affect the spatio-temporal assignment of E-UAV traffic to charging stations. This paper aims at investigating joint operations of coupled power and electric aviation transportation systems that are associated with en-route charging of E-UAVs in a centrally controlled and yet dynamic setting, i.e., with time-varying travel demand and power system base load. Dynamic E-UAV charging assignment is used as a tool to smooth the power system load. A joint pricing scheme is proposed and a cost minimization problem is formulated to achieve system optimality for such coupled systems. Numerical experiments are performed to test the proposed pricing scheme and demonstrate the benefits of the framework for joint operations.