An Alternative Algorithm for Vehicle Routing Problem with Time Windows for Daily Deliveries

This study attempts to solve vehicle routing problem with time window (VRPTW). The study first identifies the real problems and suggests some recommendations on the issues. The technique used in this study is Genetic Algorithm (GA) and initialization applied is random population method. The objective of the study is to assign a number of vehicles to routes that connect customers and depot such that the overall distance travelled is minimized and the delivery operations are completed within the time windows requested by the customers. The analysis reveals that the problems experienced in vehicle routing with time window can be solved by GA and retrieved for optimal solutions. After a thorough study on VRPTW, it is highly recommended that a company should implement the optimal routes derived from the study to increase the efficiency and accuracy of delivery with time insertion.

A novel genetic algorithm for vehicle routing problem with time windows

A novel genetic algorithm with multiple species in dynamic region is proposed,each of which occupies a dynamic region determined by the weight vector of a fuzzy adaptive Hamming neural network. Through learning and classification of genetic individuals in the evolutionary procedure,the neural network distributes multiple species into different regions of the search space. Furthermore,the neural network dynamically expands each search region or establishes new region for good offspring individuals to continuously keep the diversification of the genetic population. As a result,the premature problem inherent in genetic algorithm is alleviated and better tradeoff between the ability of exploration and exploitation can be obtained. The experimental results on the vehicle routing problem with time windows also show the good performance of the proposed genetic algorithm.

Multi-type ant system algorithm for the time dependent vehicle routing problem with time windows

The time dependent vehicle routing problem with time windows(TDVRPTW) is considered. A multi-type ant system(MTAS) algorithm hybridized with the ant colony system(ACS)and the max-min ant system(MMAS) algorithms is proposed. This combination absorbs the merits of the two algorithms in solutions construction and optimization separately. In order to improve the efficiency of the insertion procedure, a nearest neighbor selection(NNS) mechanism, an insertion local search procedure and a local optimization procedure are specified in detail. And in order to find a balance between good scouting performance and fast convergence rate, an adaptive pheromone updating strategy is proposed in the MTAS. Computational results confirm the MTAS algorithm's good performance with all these strategies on classic vehicle routing problem with time windows(VRPTW) benchmark instances and the TDVRPTW instances, and some better results especially for the number of vehicles and travel times of the best solutions are obtained in comparison with the previous research.

Development of an Efficient Genetic Algorithm for the Time Dependent Vehicle Routing Problem with Time Windows

This research considers the time-dependent vehicle routing problem (TDVRP). The time-dependent VRP does not assume constant speeds of the vehicles. The speeds of the vehicles vary during the various times of the day, based on the traffic conditions. During the periods of peak traffic hours, the vehicles travel at low speeds and during non-peak hours, the vehicles travel at higher speeds. A survey by TCI and IIM-C (2014) found that stoppage delay as percentage of journey time varied between five percent and 25 percent, and was very much dependent on the characteristics of routes. Costs of delay were also estimated and found not to affect margins by significant amounts. This study aims to overcome such problems arising out of traffic congestions that lead to unnecessary delays and hence, loss in customers and thereby valuable revenues to a company. This study suggests alternative routes to minimize travel times and travel distance, assuming a congestion in traffic situation. In this study, an efficient GA-based algorithm has been developed for the TDVRP, to minimize the total distance travelled, minimize the total number of vehicles utilized and also suggest alternative routes for congestion avoidance. This study will help to overcome and minimize the negative effects due to heavy traffic congestions and delays in customer service. The proposed algorithm has been shown to be superior to another existing algorithm in terms of the total distance travelled and also the number of vehicles utilized. Also the performance of the proposed algorithm is as good as the mathematical model for small size problems.

A GA approach to vehicle routing problem with time windows considering loading constraints

As a new variant of vehicle routing problem( VRP),a finished vehicle routing problem with time windows in finished vehicle logistics( FVRPTW) is modeled and solved. An optimization model for FVRPTW is presented with the objective of scheduling multiple transport routes considering loading constraints along with time penalty function to minimize the total cost. Then a genetic algorithm( GA) is developed. The specific encoding and genetic operators for FVRPTW are devised.Especially,in order to accelerate its convergence,an improved termination condition is given. Finally,a case study is used to evaluate the effectiveness of the proposed algorithm and a series of experiments are conducted over a set of finished vehicle routing problems. The results demonstrate that the proposed approach has superior performance and satisfies users in practice. Contributions of the study are the modeling and solving of a complex FVRPTW in logistics industry.

Improved Multi-Agent System for the Vehicle Routing Problem with Time Windows

The vehicle routing problem with time windows (VRPTW) involves assigning a fleet of limited capacity vehicles to serve a set of customers without violating the capacity and time constraints. This paper presents a multi-agent model system for the VRPTW based on the internal behavior of agents and coordination among the agents. The system presents a formal view of coordination using the traditional contract-net protocol (CNP) that relies on the basic loop of agent behavior for order receiving, order announcement, bid calculation, and order scheduling followed by order execution. An improved CNP method based on a vehicle selection strategy is used to reduce the number of negotiations and the negotiation time. The model is validated using Solomon's benchmarks, with the results showing that the improved CNP uses only 30% as many negotiations and only 70% of the negotiation time of the traditional CNP.

Research on Vehicle Routing Problem with Soft Time Windows Based on Hybrid Tabu Search and Scatter Search Algorithm

With the expansion of the application scope of social computing problems,many path problems in real life have evolved from pure path optimization problems to social computing problems that take into account various social attributes,cultures,and the emotional needs of customers.The actual soft time window vehicle routing problem,speeding up the response of customer needs,improving distribution efficiency,and reducing operating costs is the focus of current social computing problems.Therefore,designing fast and effective algorithms to solve this problem has certain theoretical and practical significance.In this paper,considering the time delay problem of customer demand,the compensation problem is given,and the mathematical model of vehicle path problem with soft time window is given.This paper proposes a hybrid tabu search(TS)&scatter search(SS)algorithm for vehicle routing problem with soft time windows(VRPSTW),which mainly embeds the TS dynamic tabu mechanism into the SS algorithm framework.TS uses the scattering of SS to avoid the dependence on the quality of the initial solution,and SS uses the climbing ability of TS improves the ability of optimizing,so that the quality of search for the optimal solution can be significantly improved.The hybrid algorithm is still based on the basic framework of SS.In particular,TS is mainly used for solution improvement and combination to generate new solutions.In the solution process,both the quality and the dispersion of the solution are considered.A simulation experiments verify the influence of the number of vehicles and maximum value of tabu length on solution,parameters’control over the degree of convergence,and the influence of the number of diverse solutions on algorithm performance.Based on the determined parameters,simulation experiment is carried out in this paper to further prove the algorithm feasibility and effectiveness.The results of this paper provide further ideas for solving vehicle routing problems with time windows and improving the efficiency of vehicle routing problems and have strong applicability.

REFINEMENTS OF THE COLUMN GENERATION PROCESS FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

The Vehicle Routing Problem with Time Windows is a generalization of the well known capacity constrained Vehicle Routing Problem. A homogeneous fleet of vehicles has to service a set of customers. The service of the customers can only start within a well-defined time interval denoted the time window. The objective is to determine routes for the vehicles that minimizes the accumulated cost (or distance). Currently the best approaches for determining optimal solutions are based on column generation and Branch-and-Bound, also known as Branch-and-Price. This paper presents two ideas for run-time improvements of the Branch-and-Price framework for the Vehicle Routing Problem with Time Windows. Both ideas reveal a significant potential for run-time refinements when speeding up an exact approach without compromising optimality.

Robust Electric Vehicle Routing Problem with Time Windows under Demand Uncertainty and Weight-Related Energy Consumption

Vehicle routing problem with time windows(VRPTW)is a core combinatorial optimization problem in distribution tasks.The electric vehicle routing problem with time windows under demand uncertainty and weight-related energy consumption is an extension of the VRPTW.Although some researchers have studied either the electric VRPTW with nonlinear energy consumption model or the impact of the uncertain customer demand on the conventional vehicles,the literature on the integration of uncertain demand and energy consumption of electric vehicles is still scarce.However,practically,it is usually not feasible to ignore the uncertainty of customer demand and the weight-related energy consumption of electronic vehicles(EVs)in actual operation.Hence,we propose the robust optimization model based on a route-related uncertain set to tackle this problem.Moreover,adaptive large neighbourhood search heuristic has been developed to solve the problem due to the NP-hard nature of the problem.The effectiveness of the method is verified by experiments,and the influence of uncertain demand and uncertain parameters on the solution is further explored.

A metaheuristic method for the multireturn-to-depot petrol truck routing problem with time windows

The petrol truck routing problem is an important part of the petrol supply chain.This study focuses on determining routes for distributing petrol products from a depot to petrol stations with the objective of minimizing the total travel cost and the fixed cost required to use the trucks.We propose a mathematical model that considers petrol trucks returning to a depot multiple times and develop a heuristic algorithm based on a local branch-and-bound search with a tabu list and the Metropolis acceptance criterion.In addition,an approach that accelerates the solution process by adding several valid inequalities is presented.In this study,the trucks are homogeneous and have two compartments,and each truck can execute at most three tasks daily.The sales company arranges the transfer amount and the time windows for each station.The performance of the proposed algorithm is evaluated by comparing its results with the optimal results.In addition,a real-world case of routing petrol trucks in Beijing is studied to demonstrate the effectiveness of the proposed approach.

Vehicle routing problem with time-varying speed

Vehicle routing problem with time-varying speed ( VRPTS) is a generalization of vehicle routing problem in which the travel speed between two locations depends on the passing areas and the time of a day. This paper proposes a simple model for estimating time-varying travel speeds in VRPTS that relieves much burden to the data-related problems. The study further presents three heuristics ( saving technique,proximity priority searching technique,and insertion technique) for VRPTS,developed by extending and modifying the existing heuristics for conventional VRP. The results of computational experiments demonstrate that the proposed estimation model performs well and the saving technique is the best among the three heuristics.

Weapon configuration, allocation and route planning with time windows for multiple unmanned combat air vehicles

Unmanned combat air vehicles(UCAVs) mission planning is a fairly complicated global optimum problem. Military attack missions often employ a fleet of UCAVs equipped with weapons to attack a set of known targets. A UCAV can carry different weapons to accomplish different combat missions. Choice of different weapons will have different effects on the final combat effectiveness. This work presents a mixed integer programming model for simultaneous weapon configuration and route planning of UCAVs, which solves the problem optimally using the IBM ILOG CPLEX optimizer for simple missions. This paper develops a heuristic algorithm to handle the medium-scale and large-scale problems. The experiments demonstrate the performance of the heuristic algorithm in solving the medium scale and large scale problems. Moreover, we give suggestions on how to select the most appropriate algorithm to solve different scale problems.

Solving open vehicle problem with time window by hybrid column generation algorithm

This paper addresses the open vehicle routing problem with time window(OVRPTW), where each vehicle does not need to return to the depot after completing the delivery task.The optimization objective is to minimize the total distance. This problem exists widely in real-life logistics distribution process.We propose a hybrid column generation algorithm(HCGA) for the OVRPTW, embedding both exact algorithm and metaheuristic. In HCGA, a label setting algorithm and an intelligent algorithm are designed to select columns from small and large subproblems, respectively. Moreover, a branch strategy is devised to generate the final feasible solution for the OVRPTW. The computational results show that the proposed algorithm has faster speed and can obtain the approximate optimal solution of the problem with 100 customers in a reasonable time.

On Vehicle Routing Problems (VRP) with a Focus on Multiple Priorities

This paper discusses the concept of priorities based on Time and Quantity, which arise on the occasion of vehicle routing. It explains the interconnectivity between the priorities based on Time and Quantity and formulates a dynamic that shows the fusion of Time and Quantity into the Vehicle Routing Problem’s objective function. The paper focuses on the development of an expanded VRP objective function in which the priorities based on Time and Quantities are imbedded thus opens a vista of knowledge, aggregating and modelling the priorities as a mean to reduce transportation costs that lead to an organized and more timely deliveries of goods employing various of today’s proposed logistic systems coupled with widely used positioning systems.

An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem

The multi-compartment electric vehicle routing problem(EVRP)with soft time window and multiple charging types(MCEVRP-STW&MCT)is studied,in which electric multi-compartment vehicles that are environmentally friendly but need to be recharged in course of transport process,are employed.A mathematical model for this optimization problem is established with the objective of minimizing the function composed of vehicle cost,distribution cost,time window penalty cost and charging service cost.To solve the problem,an estimation of the distribution algorithm based on Lévy flight(EDA-LF)is proposed to perform a local search at each iteration to prevent the algorithm from falling into local optimum.Experimental results demonstrate that the EDA-LF algorithm can find better solutions and has stronger robustness than the basic EDA algorithm.In addition,when comparing with existing algorithms,the result shows that the EDA-LF can often get better solutions in a relatively short time when solving medium and large-scale instances.Further experiments show that using electric multi-compartment vehicles to deliver incompatible products can produce better results than using traditional fuel vehicles.

Study on the Inventory Routing Problem of Refined Oil Distribution Based on Working Time Equilibrium

Taking the distribution route optimization of refined oil as background, this paper studies the inventory routing problem of refined oil distribution based on working time equilibrium. In consideration of the constraints of vehicle capacity, time window for unloading oil, service time and demand of each gas station, we take the working time equilibrium of each vehicle as goal and establish an integer programming model for the vehicle routing problem of refined oil distribution, the objective function of the model is to minimize the maximum working time of vehicles. To solve this model, a Lingo program was written and a heuristic algorithm was designed. We further use the random generation method to produce an example with 10 gas stations. The local optimal solution and approximate optimal solution are obtained by using Lingo software and heuristic algorithm respectively. By comparing the approximate optimal solution obtained by heuristic algorithm with the local optimal solution obtained by Lingo software, the feasibility of the model and the effectiveness of the heuristic algorithm are verified. The results of this paper provide a theoretical basis for the scheduling department to formulate the oil distribution plan.

A Coordination-Based Algorithm for Dedicated Destination Vehicle Routing in B2B E-Commerce

This paper proposes a solution to the open vehicle routing problem with time windows(OVRPTW)considering third-party logistics(3PL).For the typical OVRPTW problem,most researchers consider time windows,capacity,routing limitations,vehicle destination,etc.Most researchers who previously investigated this problem assumed the vehicle would not return to the depot,but did not consider its final destination.However,by considering 3PL in the B2B e-commerce,the vehicle is required back to the nearest 3PL location with available space.This paper formulates the problem as a mixed integer linear programming(MILP)model with the objective of minimizing the total travel distance.A coordinate representation particle swarm optimization(CRPSO)algorithm is developed to obtain the best delivery sequencing and the capacity of each vehicle.Results of the computational study show that the proposed method provides solution within a reasonable amount of time.Finally,the result compared to PSO also indicates that the CRPSO is effective.

Enhanced solution representations for vehicle routing problems with split deliveries

In this study,we investigate a forest-based solution representation for split delivery vehicle routing problems(SDVRPs),which have several practical applications and are among the most difficult vehicle routing problems.The new solution representation fully reflects the nature of split delivery,and can help reduce the search space when used in heuristic algorithms.Based on the forest structure,we devise three neighborhood search operators.To highlight the effectiveness of this solution representation,we integrate these operators into a standard tabu search framework.We conduct extensive experiments on three main SDVRPs addressed in the literature:The basic SDVRP,the multidepot SDVRP,and the SDVRP with time windows.The experimental results show that the new forest-based solution representation is particularly effective in designing and implementing neighborhood operators,and that our new approach outperforms state-of-the-art algorithms on standard datasets.

面向复杂物流配送场景的车辆路径规划多任务辅助进化算法

在现代社会中,复杂物流配送场景的车辆路径规划问题(Vehicle routing problem,VRP)一般带有时间窗约束且需要提供同时取送货的服务.这种复杂物流配送场景的车辆路径规划问题是NP-难问题.当其规模逐渐增大时,一般的数学规划方法难以求解,通常使用启发式方法在限定时间内求得较优解.然而,传统的启发式方法从原大规模问题直接开始搜索,无法利用先前相关的优化知识,导致收敛速度较慢.因此,提出面向复杂物流配送场景的车辆路径规划多任务辅助进化算法(Multitask-based assisted evolutionary algorithm,MBEA),通过使用迁移优化方法加快算法收敛速度,其主要思想是通过构造多个简单且相似的子任务用于辅助优化原大规模问题.首先从原大规模问题中随机选择一部分客户订单用于构建多个不同的相似优化子任务,然后使用进化多任务(Evolutional multitasking,EMT)方法用于生成原大规模问题和优化子任务的候选解.由于优化子任务相对简单且与原大规模问题相似,其搜索得到的路径特征可以通过任务之间的知识迁移辅助优化原大规模问题,从而加快其求解速度.最后,提出的算法在京东物流公司快递取送货数据集上进行验证,其路径规划效果优于当前最新提出的路径规划算法.