Optimal Information Location for Adaptive Routing

One strategy for addressing uncertain roadway conditions and travel times is to provide real-time travel information to drivers through variable message signs, highway advisory radio, or other means. However, providing such information is often costly, and decisions must be made about the most useful places to inform drivers about local conditions. This paper addresses this question, building on adaptive routing algorithms describing optimal traveler behavior in stochastic networks with en route information. Three specific problem contexts are formulated: routing of a single vehicle, assignment of multiple vehicles in an uncongested network, and adaptive equilibrium with congestion. A network contraction procedure is described which makes an enumerative algorithm computationally feasible for small-to-medium sized roadway networks, along with heuristics which can be applied for large-scale networks. These algorithms are demonstrated on three networks of varying size.     

Adaptive Park-and-ride Choice on Time-dependent Stochastic Multimodal Transportation Network

In transportation networks with stochastic and dynamic travel times, park-and-ride decisions are often made adaptively considering the realized state of traffic. That is, users continue driving towards their destination if the congestion level is low, but may consider taking transit when the congestion level is high. This adaptive behavior determines whether and where people park-and-ride. We propose to use a Markov decision process to model the problem of commuters’ adaptive park-and-ride choice behavior in a transportation network with time-dependent and stochastic link travel times. The model evaluates a routing policy by minimizing the expected cost of travel that leverages the online information about the travel time on outgoing links in making park-and-ride decisions. We provide a case study of park-and-ride facilities located on freeway I-394 in Twin Cities, Minnesota. The results show a significant improvement in the travel time by the use of park-and-ride during congested conditions. It also reveals the time of departure, the state of the traffic, and the location from where park-and-ride becomes an attractive option to the commuters. Finally, we show the benefit of using online routing in comparison to an offline routing algorithm.

     

Distributed dynamic lane reversal and rerouting for traffic delay reduction

Traffic congestion is a major source of delays in modern road networks. Motivated by this, we propose two distributed algorithms to reduce delays: a dynamic lane reversal algorithm and a rerouting algorithm. When there is a density imbalance on a road, time can be saved by reallocating lanes from the less dense side to the more dense side, which motivates dynamic lane reversal. When a road has greater density than nearby roads, time can be saved by redirecting flow into the least congested roads, this motivates dynamic rerouting. Given a communication system between infrastructure and vehicles on the road, the local state of the network can be approximated and utilised by the algorithms to minimise travel time. In order to provide a better fundamental understanding of the system dynamics, we analyse equilibrium conditions for the system and prove convergence of the lane reversal algorithm to a critical point. Overall performance is also examined in simulation.     

Simultaneous control of vehicle routing and inventory for dynamic inbound supply chain

This paper investigates inbound logistics for an OEM (Original Equipment Manufacturing) manufacturer, who aims at short production time and JIT policy. In such a case, it can be argued that the inbound vehicle routing schedule should be combined with incoming parts inventory control. In this paper, we propose a simultaneous control method of combining vehicle scheduling and inventory control for such dynamic inbound logistics. For the transportation control, a vehicle routing system, in which delivery jobs are made with shipments of one supplier, is proposed to generate a vehicle routes plan by considering production start time, travel time, waiting time, and loading/unloading time. To evaluate the performance of the generated vehicle routing plan, a goal model is also developed by considering vehicle operating cost, stock level exceeding penalty, and transportation efficiency. A generated vehicle routing plan can be rejected when the stock level is over the capacity and an appropriate number of vehicles for its manufacturing environment can be determined. Using real data from an LCD firm, a simulation study is conducted. The simulation results indicate that the simultaneous control approach requires fewer vehicles than the existing system and shows better efficiency of transportation. This method can also be used to determine the appropriate incoming part inventory level or the number of vehicles required in dynamic inbound logistics.     

Multicriteria Stochastic Shortest Path Problem for Electric Vehicles

This paper formulates the reliable routing of electric vehicles in stochastic networks as a multicriteria shortest path problem with travel time and charging cost components. The reliability term is defined as the probability of finishing the trip without running out of charge. The arc travel times are represented as stochastic variables, and arc energy consumption is modeled as a linear function of arc length and arc travel time. The traveler aims to minimize the generalized cost, formulated as a linear function of travel time and charging cost, subject to a minimum reliability threshold, representing the level of risk a traveler is willing to take in favor of routes with lower cost. We propose a solution algorithm based on generalized dynamic programming and show that the optimal solution may include cycles that visit at least one charging station. The properties of the proposed multicriteria shortest path problem are mathematically proved. The simulation results on randomly-generated networks show that cyclic paths are very rare, and that the generalized cost of travel is a monotone increasing function of minimum reliability threshold.     

F-Ant: an effective routing protocol for ant colony optimization based on fuzzy logic in vehicular ad hoc networks

Vehicular ad hoc networks (VANETs) are a subset of mobile ad hoc networks that provide communication services between nearby vehicles and also between vehicles and roadside infrastructure. These networks improve road safety and accident prevention and provide entertainment for passengers of vehicles. Due to the characteristics of VANET such as self-organization, dynamic nature and fast-moving vehicles, routing in this network is a considerable challenge. Swarm intelligence algorithms (nature-inspired) such as ant colony optimization (ACO) have been proposed for developing routing protocols in VANETs. In this paper, we propose an enhanced framework for ACO protocol based on fuzzy logic for VANETs. To indicate the effectiveness and performance of our proposed protocol, the network simulator NS-2 is used for simulation. The simulation results demonstrate that our proposed protocol achieves high data packet delivery ratio and low end-to-end delay compared to traditional routing algorithms such as ACO and ad hoc on-demand distance vector (AODV).

     

A general framework for modeling shared autonomous vehicles with dynamic network-loading and dynamic ride-sharing application

Shared autonomous vehicles (SAVs) could provide low-cost service to travelers and possibly replace the need for personal vehicles. Previous studies found that each SAV could service multiple travelers, but many used unrealistic congestion models, networks, and/or travel demands. The purpose of this paper is to provide a method for future research to use realistic flow models to obtain more accurate predictions about SAV benefits. This paper presents an event-based framework for implementing SAV behavior in existing traffic simulation models. We demonstrate this framework in a cell transmission model-based dynamic network loading simulator. We also study a heuristic approach for dynamic ride-sharing. We compared personal vehicles and SAV scenarios on the downtown Austin city network. Without dynamic ride-sharing, the additional empty repositioning trips made by SAVs increased congestion and travel times. However, dynamic ride-sharing resulted in travel times comparable to those of personal vehicles because ride-sharing reduced vehicular demand. Overall, the results show that using realistic traffic flow models greatly affects the predictions of how SAVs will affect traffic congestion and travel patterns. Future work should use a framework such as the one in this paper to integrate SAVs with established traffic flow simulators.     

Implementation of K-Means Algorithm and Dynamic Routing Protocol in VANET

With the growth of Vehicular Ad-hoc Networks, many services delivery is gaining more attention from the intelligent transportation system. However, mobility characteristics of vehicular networks cause frequent disconnection of routes, especially during the delivery of data. In both developed and developing countries, a lot of time is consumed due to traffic congestion. This has significant negative consequences, including driver stress due to increased time demand, decreased productivity for various personalized and commercial vehicles, and increased emissions of hazardous gases especially air polluting gases are impacting public health in highly populated areas. Clustering is one of the most powerful strategies for achieving a consistent topological structure. Two algorithms are presented in this research work. First, a k-means clustering algorithm in which dynamic grouping by k-implies is performed that fits well with Vehicular network’s dynamic topology characteristics. The suggested clustering reduces overhead and traffic management. Second, for inter and intra-clustering routing, the dynamic routing protocol is proposed, which increases the overall Packet Delivery Ratio and decreases the End-to-End latency. Relative to the cluster-based approach, the proposed protocol achieves improved efficiency in terms of Throughput, Packet Delivery Ratio, and End-to-End delay parameters comparing the situations by taking different number of vehicular nodes in the network.     

A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service

On-time shipment delivery is critical for just-in-time production and quick response logistics. Due to uncertainties in travel and service times, on-time arrival probability of vehicles at customer locations can not be ensured. Therefore, on-time shipment delivery is a challenging job for carriers in congested road networks. In this paper, such on-time shipment delivery problems are formulated as a stochastic vehicle routing problem with soft time windows under travel and service time uncertainties. A new stochastic programming model is proposed to minimize carrier’s total cost, while guaranteeing a minimum on-time arrival probability at each customer location. The aim of this model is to find a good trade-off between carrier’s total cost and customer service level. To solve the proposed model, an iterated tabu search heuristic algorithm was developed, incorporating a route reduction mechanism. A discrete approximation method is proposed for generating arrival time distributions of vehicles in the presence of time windows. Several numerical examples were conducted to demonstrate the applicability of the proposed model and solution algorithm.     

Minimum cost VRP with time-dependent speed data and congestion charge

A heuristic algorithm, called LANCOST, is introduced for vehicle routing and scheduling problems to minimize the total travel cost, where the total travel cost includes fuel cost, driver cost and congestion charge. The fuel cost required is influenced by the speed. The speed for a vehicle to travel along any road in the network varies according to the time of travel. The variation in speed is caused by congestion which is greatest during morning and evening rush hours. If a vehicle enters the congestion charge zone at any time, a fixed charge is applied. A benchmark dataset is designed to test the algorithm. The algorithm is also used to schedule a fleet of delivery vehicles operating in the London area.     

A dynamic vehicle routing problem with time-dependent travel times

In this paper we present a formulation for the dynamic vehicle routing problem with time-dependent travel times. We also present a genetic algorithm to solve the problem. The problem is a pick-up or delivery vehicle routing problem with soft time windows in which we consider multiple vehicles with different capacities, real-time service requests, and real-time variations in travel times between demand nodes.The performance of the genetic algorithm is evaluated by comparing its results with exact solutions and lower bounds for randomly generated test problems. For small size problems with up to 10 demands, the genetic algorithm provides almost the same results as the exact solutions, while its computation time is less than 10% of the time required to produce the exact solutions. For the problems with 30 demand nodes, the genetic algorithm results have less than 8% gap with lower bounds.This research also shows that as the uncertainty in the travel time information increases, a dynamic routing strategy that takes the real-time traffic information into account becomes increasingly superior to a static one. This is clear when we compare the static and dynamic routing strategies in problem scenarios that have different levels of uncertainty in travel time information. In additional tests on a simulated network, the proposed algorithm works well in dealing with situations in which accidents cause significant congestion in some part of the transportation network.     

SALA: A Self-Adaptive Learning Algorithm—Towards Efficient Dynamic Route Guidance in Urban Traffic Networks

In order to alleviate traffic congestion for vehicles in urban networks, most of current researches mainly focused on signal optimization models and traffic assignment models, or tried to recognize the interaction between signal control and traffic assignment. However, these methods may not be able to provide fast and accurate route guidance due to the lack of individual traffic demands, real-time traffic data and dynamic cooperation between vehicles. To solve these problems, this paper proposes a dynamic and real-time route selection model in urban traffic networks (DR2SM), which can supply a more accurate and personalized strategy for vehicles in urban traffic networks. Combining the preference for alternative routes with real-time traffic conditions, each vehicle in urban traffic networks updates its route selection before going through each intersection. Based on its historical experiences and estimation about route choices of the other vehicles, each vehicle uses a self-adaptive learning algorithm to play congestion game with each other to reach Nash equilibrium. In the route selection process, each vehicle selects the user-optimal route, which can maximize the utility of each driving vehicle. The results of the experiments on both synthetic and real-world road networks show that compared with non-cooperative route selection algorithms and three state-of-the-art equilibrium algorithms, DR2SM can effectively reduce the average traveling time in the dynamic and uncertain urban traffic networks.     

A Dynamic Road Incident Information Delivery Strategy to Reduce Urban Traffic Congestion

Advanced information and communication technologies can be used to facilitate traffic incident management. If an incident is detected and blocks a road link, in order to reduce the incident-induced traffic congestion, a dynamic strategy to deliver incident information to selected drivers and help them make detours in urban areas is proposed by this work. Time-dependent shortest path algorithms are used to generate a subnetwork where vehicles should receive such information. A simulation approach based on an extended cell transmission model is used to describe traffic flow in urban networks where path information and traffic flow at downstream road links are well modeled. Simulation results reveal the influences of some major parameters of an incident-induced congestion dissipation process such as the ratio of route-changing vehicles to the total vehicles, operation time interval of the proposed strategy, traffic density in the traffic network, and the scope of the area where traffic incident information is delivered. The results can be used to improve the state of the art in preventing urban road traffic congestion caused by incidents.      

Iterated local search and simulated annealing algorithms for the inventory routing problem

This paper addresses the inventory routing problem (IRP), which consists in defining the customer visit schedule, the delivery quantities, and the vehicle routing plan to meet the demands of a set of customers over a given time horizon. We consider the variant with a single item, a single supplier, multiple vehicles, and a finite multiperiod planning horizon, minimizing the sum of inventory and travel costs. In addition, we address an alternative objective function that minimizes the logistic ratio, defined as the total travel cost divided by the total quantity delivered to customers. This second objective function, while more realistic in some logistics settings, poses a challenge for integer programming models and exact methods because of its nonlinearity. To our knowledge, no heuristic method has been proposed to address this objective in the IRP variant addressed in this paper. To solve this problem with each of these objective functions, we propose effective metaheuristic algorithms based on iterated local search and simulated annealing. Computational experiments show that these algorithms provide reasonably high‐quality solutions in relatively short running times for both objective functions when compared to other methods for well‐known instances from the literature. Moreover, the algorithms produce new best solutions for some of these instances.     

具有路由性能和蚁群优化的移动P2P路由策略*

目前的移动P2P网络路由策略不能较好适应网络拓扑结构的动态多变、网络和移动设备的资源有限等特点,以及不能较好解决路由建立和维护所带来的网络拥塞和资源消耗。针对上述问题,采用有限洪泛路由查询和移动agent路由查询相结合的策略,为每个移动节点提供丰富可靠、及时高效的路由信息。同时,使用改进的蚁群算法,综合考虑网络带宽、时延等多个路由性能指标,作为路由策略中路由选择机制。仿真研究证明,将所提出的理论与方法应用于移动P2P的路由选择和维护等问题,本算法在控制消息的开销、平均响应效率等方面具有良好的性能,对于网络     

行驶时间和服务时间随机的集配货一体的分批配送车辆路径优化

将铁路物流中心集配货路径问题抽象为行驶时间和服务时间随机的集送货一体的分批配送车辆路径问题进行优化.根据问题特点建立带修正的随机规划模型,对迭代局部搜索算法进行改进,设计允许分批配送的初始解构造算法、局部搜索算法和扰动机制.算例测试证实:分批配送在中等规模和大规模算例中能发挥较好的作用,大部分中等规模和大规模算例都比不允许分批配送时所得到的解更优,部分中等规模和大规模算例车辆数有所减少;配送点数随着算例规模的扩大而增加,但是配送点数占顾客点数的比例却逐步降低;随机因素随机性增加将导致目标函数增大,对分批配送点数的影响不大.     

Decremental algorithm for adaptive routing incorporating traveler information

Routing in a stochastic and dynamic (time-dependent) network is a crucial transportation problem. A new variant of adaptive routing, which assumes perfect online information of continuous real-time link travel time, is proposed. Driver's speed profile is taken into consideration to realistically estimate travel times, which also involves the stochasticity of links in a dynamic network. An adaptive approach is suggested to tackle the continuous dynamic shortest path problem. A decremental algorithm is consequently developed to reduce optimization time. The impact of the proposed adaptive routing and the performance of the decremental approach are evaluated in static and dynamic networks under different traffic conditions. The proposed approach can be incorporated into vehicle navigation systems.     

A Mathematical Framework for Designing a Low-Loss, Low-Delay Internet

We survey some recent results on modeling, analysis and design of congestion control schemes for the Internet. Using tools from convex optimization and control theory, we show that congestion controllers can be viewed as distributed algorithms for achieving fair resource allocation among competing sources. We illustrate the use of simple mathematical models to analyze the behavior of currently deployed Internet congestion control protocols as well as to design new protocols for networks with large capacities, delays and general topology. These new protocols are designed to nearly eliminate loss and queueing delay in the Internet, yet achieving high utilization and any desired fairness.     

Dynamic routing strategies for JIT production in hybrid flow shops

In production processes, just-in-time (JIT) completion of jobs helps reduce both the inventory and late delivery of finished products. Previous research which aims to achieve JIT job completion mainly worked on static scheduling problems, in which all jobs are available from time zero or the available time of each job is known beforehand. In contrast, dynamic scheduling problems which involve continual arrival of new jobs are not much researched and dispatching rules remain the most frequently used method for such problems. However, dispatching rules are not high-performing for the JIT objective. This study proposes several routing strategies which can help dispatching rules realize JIT completion for jobs arriving dynamically in hybrid flow shops. The routing strategies are based on distributed computing which makes realtime forecast of completion times of unfinished jobs. The advantages include short computing time, quick response and robustness against disturbance. Computer simulations show that the performance of dispatching rules combined with the proposed routing strategies is significantly higher than that of dispatching rules only and that of dispatching rules combined with the previous routing methods.     

Solution time reduction techniques of a stochastic dynamic programming approach for hazardous material route selection problem

We use a stochastic dynamic programming (SDP) approach to solve the problem of determining the optimal routing policies in a stochastic dynamic network. Due to its long time for solving SDP, we propose three techniques for pruning stochastic dynamic networks to expedite the process of obtaining optimal routing policies. The techniques include: (1) use of static upper/lower bounds, (2) pre-processing the stochastic dynamic networks by using the start time and origin location of the vehicle, and (3) a mix of pre-processing and upper/lower bounds. Our experiments show that while finding optimal routing policies in stochastic dynamic networks, the last two of the three strategies have a significant computational advantage over conventional SDP. Our main observation from these experiments was that the computational advantage of the pruning strategies that depend on the start time of the vehicle varies according to the time input to the problem. We present the results of this variation in the experiments section. We recommend that while comparing the computational performances of time-dependent techniques, it is very important to test the performance of such strategies at various time inputs.