Modeling techniques for periodic vehicle routing problems

This paper presents a continuous approximation model for the period vehicle routing problem with service choice (PVRP-SC). The PVRP-SC is a variant of the period vehicle routing problem in which the visit frequency to nodes is a decision of the model. This variation can result in more efficient vehicle tours and/or greater service benefit to customers. We present a continuous approximation model to facilitate strategic and tactical planning of periodic distribution systems and evaluate the value of service choice. Further, results from the continuous model can provide guidelines for constructing solutions to the discrete PVRP-SC.     

The time-dependent pollution-routing problem

The Time-Dependent Pollution-Routing Problem (TDPRP) consists of routing a fleet of vehicles in order to serve a set of customers and determining the speeds on each leg of the routes. The cost function includes emissions and driver costs, taking into account traffic congestion which, at peak periods, significantly restricts vehicle speeds and increases emissions. We describe an integer linear programming formulation of the TDPRP and provide illustrative examples to motivate the problem and give insights about the tradeoffs it involves. We also provide an analytical characterization of the optimal solutions for a single-arc version of the problem, identifying conditions under which it is optimal to wait idly at certain locations in order to avoid congestion and to reduce the cost of emissions. Building on these analytical results we describe a novel departure time and speed optimization algorithm for the cases when the route is fixed. Finally, using benchmark instances, we present results on the computational performance of the proposed formulation and on the speed optimization procedure.     

The fleet size and mix pollution-routing problem

This paper introduces the fleet size and mix pollution-routing problem which extends the pollution-routing problem by considering a heterogeneous vehicle fleet. The main objective is to minimize the sum of vehicle fixed costs and routing cost, where the latter can be defined with respect to the cost of fuel and CO₂ emissions, and driver cost. Solving this problem poses several methodological challenges. To this end, we have developed a powerful metaheuristic which was successfully applied to a large pool of realistic benchmark instances. Several analyses were conducted to shed light on the trade-offs between various performance indicators, including capacity utilization, fuel and emissions and costs pertaining to vehicle acquisition, fuel consumption and drivers. The analyses also quantify the benefits of using a heterogeneous fleet over a homogeneous one.     

The Pollution-Routing Problem

The amount of pollution emitted by a vehicle depends on its load and speed, among other factors. This paper presents the Pollution-Routing Problem (PRP), an extension of the classical Vehicle Routing Problem (VRP) with a broader and more comprehensive objective function that accounts not just for the travel distance, but also for the amount of greenhouse emissions, fuel, travel times and their costs. Mathematical models are described for the PRP with or without time windows and computational experiments are performed on realistic instances. The paper sheds light on the tradeoffs between various parameters such as vehicle load, speed and total cost, and offers insight on economies of ‘environmental-friendly’ vehicle routing. The results suggest that, contrary to the VRP, the PRP is significantly more difficult to solve to optimality but has the potential of yielding savings in total cost.     

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

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

Platooning on two-lane two-way highways: An empirical investigation

This paper presents an empirical investigation into platooning on two-lane two-way highways. The main objective is to better understand this phenomenon that has important implications on traffic performance and safety. Field data from three study sites in the state of Montana were used in this study. Separate investigations were performed to examine the relationships among platoon-related variables, namely; time headway, travel speed, and platoon size. The study confirmed that interaction between successive vehicles in the traffic stream generally diminishes beyond a time headway threshold value that fell in the range of 5–7 seconds. Also, the study revealed that very short headways (less than one second) are more associated with aggressive driving and higher speeds than with slow-moving platoons due to lack of passing opportunities. Further, the study found that amount of impedance to traffic is proportional to the size of platoon as evidenced by the relative difference between mean speed of various size platoons and the mean speed of unimpeded vehicles. The study provided other valuable insights into the platooning phenomenon on two-lane highways that are essential in developing a better understanding of traffic operation on two-lane highways.     

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.