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.     

Vehicle routing with roaming delivery locations

We propose the vehicle routing problem with roaming delivery locations (VRPRDL) to model an innovation in last-mile delivery where a customer’s order is delivered to the trunk of his car. We develop construction and improvement heuristics for the VRPRDL based on two problem-specific techniques: (1) efficiently optimizing the delivery locations for a fixed customer delivery sequence and (2) efficiently switching a predecessor’s or successor’s delivery location during the insertion or deletion of a customer in a route. Furthermore, we conduct an extensive computation study to assess and quantify the benefits of trunk delivery in a variety of settings. The study reveals that a significant reduction in total distance travelled can be achieved, especially when trunk delivery is combined with traditional home delivery, which has both economic and environmental benefits.     

Partial recharge strategies for the electric vehicle routing problem with time windows

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension to the well-known Vehicle Routing Problem with Time Windows (VRPTW) where the fleet consists of electric vehicles (EVs). Since EVs have limited driving range due to their battery capacities they may need to visit recharging stations while servicing the customers along their route. The recharging may take place at any battery level and after the recharging the battery is assumed to be full. In this paper, we relax the full recharge restriction and allow partial recharging (EVRPTW-PR), which is more practical in the real world due to shorter recharging duration. We formulate this problem as a 0–1 mixed integer linear program and develop an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it efficiently. We apply several removal and insertion mechanisms by selecting them dynamically and adaptively based on their past performances, including new mechanisms specifically designed for EVRPTW and EVRPTW-PR. These new mechanisms include the removal of the stations independently or along with the preceding or succeeding customers and the insertion of the stations with determining the charge amount based on the recharging decisions. We test the performance of ALNS by using benchmark instances from the recent literature. The computational results show that the proposed method is effective in finding high quality solutions and the partial recharging option may significantly improve the routing decisions.     

Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign AVs to immediate traveler demand requests

Motivated by the growth of ridesourcing services and the expected advent of fully-autonomous vehicles (AVs), this paper defines, models, and compares assignment strategies for a shared-use AV mobility service (SAMS). Specifically, the paper presents the on-demand SAMS with no shared rides, defined as a fleet of AVs, controlled by a central operator, that provides direct origin-to-destination service to travelers who request rides via a mobile application and expect to be picked up within a few minutes. The underlying operational problem associated with the on-demand SAMS with no shared rides is a sequential (i.e. dynamic or time-dependent) stochastic control problem. The AV fleet operator must assign AVs to open traveler requests in real-time as traveler requests enter the system dynamically and stochastically. As there is likely no optimal policy for this sequential stochastic control problem, this paper presents and compares six AV-traveler assignment strategies (i.e. control policies). An agent-based simulation tool is employed to model the dynamic system of AVs, travelers, and the intelligent SAMS fleet operator, as well as, to compare assignment strategies across various scenarios. The results show that optimization-based AV-traveler assignment strategies, strategies that allow en-route pickup AVs to be diverted to new traveler requests, and strategies that incorporate en-route drop-off AVs in the assignment problem, reduce fleet miles and decrease traveler wait times. The more-sophisticated AV-traveler assignment strategies significantly improve operational efficiency when fleet utilization is high (e.g. during the morning or evening peak); conversely, when fleet utilization is low, simply assigning traveler requests sequentially to the nearest idle AV is comparable to more-advanced strategies. Simulation results also indicate that the spatial distribution of traveler requests significantly impacts the empty fleet miles generated by the on-demand SAMS.     

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.     

多出口路由策略实现及相关问题研究

研究了校园网多出口的需求产生及面临的问题，对比了三种可能的方法，提出了较合理的配置方案，该方案利用了静态路由优先级、网络地址转换、基于策略的路由、VLAN及访问控制列表等多种技术，实现了路由链路备份、访问速度提升，降低国际流量计费．     

Intelligent Iterated Local Search Methods for Solving Vehicle Routing Problem with Different Fleets

Introduction Vehicle routing problem (VRP) with differentfleets is an important investment decision in reality. Itconsists of two decision-making processes: selectingvehicles of available types and routing the selectedfleet. A desirable fleet has more than one type of ve-hicles. Typically, the fixed cost of vehicles accountsfor approximately 80% of the total cost associatedwith vehicles[1]. The fixed cost is a major factor todetermine vehicle combination in a fleet.A few models were develope…     

多目标多重运输调度问题的混合算法

本文研究了多目标多重运输调度问题．建立了该问题的目标规划模型，提出了该问题基于分校定界和割平面技术的混合算法。     

FAST UPDATE ALGORITHM FOR TCAM-BASED ROUTING LOOKUPS

Introduction　　 The higher bandwidth need requires fastercommunication links and faster network router.The central bottlenecks in router are link speeds,switching and routing lookups. Readily availablesolutions exist for the first two factors:for exam-ple,fiber- optic cables can provide faster links.Switching was well studied and the good solutionslike fast busses and crossbar switches were devel-oped[1,2 ] .Thus the major remaining bottleneck isfast routing lookups. Fast forwarding engines,…     

Overview of Stochastic Vehicle Routing Problems

Stochastic vehicle routing problems (VRPs) play important roles in logistics, though they have not been studied systematically yet. The paper summaries the definition, properties and classification of stochastic VRPs, makes further discussion about two strategies in stochastic VRPs, and at last overviews dynamic and stochastic VRPs.