A particle swarm optimization algorithm for open vehicle routing problem

This paper presents a real-value version of particle swarm optimization (PSO) for solving the open vehicle routing problem (OVRP) that is a well-known combinatorial optimization problem. In OVRP a vehicle does not return to the depot after servicing the last customer on a route. A particular decoding method is proposed for implementing PSO for OVRP. In the decoding method, a vector of the customer’s position is constructed in descending order. Then each customer is assigned to a route with taking into account feasibility conditions. Finally one-point move has been applied on constructed routes that seem promising to result in a better solution. Experimental evaluations on benchmark data sets demonstrate the competitiveness of the proposed algorithm.     

OVRP_GELS: solving open vehicle routing problem using the gravitational emulation local search algorithm

In open vehicle routing problem (OVRP), after delivering service to the last customer, the vehicle does not necessarily return to the initial depot. This type of problem originally defined about thirty years ago and still is an open issue. In real life, the OVRP is similar to the delivering newspapers and consignments. The problem of service delivering to a set of customers is a particular open VRP with an identical fleet for transporting vehicles that do not necessarily return to the initial depot. Contractors which are not the employee of the delivery company use their own vehicles and do not return to the depot. Solving the OVRP means to optimize the number of vehicles, the traveling distance and the traveling time of a vehicle. In time, several algorithms such as tabu search, deterministic annealing and neighborhood search were used for solving the OVRP. In this paper, a new combinatorial algorithm named OVRP_GELS based on gravitational emulation local search algorithm for solving the OVRP is proposed. We also used record-to-record algorithm to improve the results of the GELS. Several numerical experiments show a good performance of the proposed method for solving the OVRP when compared with existing techniques.

     

An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup

In this paper we use an ant colony system (ACS) algorithm to solve the vehicle routing problem with simultaneous delivery and pickup (VRPSDP) which is a combinatorial optimization problem. ACS is an algorithmic approach inspired by the foraging behavior of real ants. Artificial ants are used to construct a solution for the problem by using the pheromone information from previously generated solutions. The proposed ACS algorithm uses a construction rule as well as two multi-route local search schemes. The algorithm can also solve the vehicle routing problem with backhaul and mixed load (VRPBM). An extensive numerical experiment is performed on benchmark problem instances available in literature. It is found that ACS gives good results compared to the existing algorithms.     

需求可拆分车辆路径问题的聚类求解算法

针对传统的车辆路径问题通常假设客户的需求不能拆分,即客户的需求由一辆车满足,而实际上通过需求的拆分可使需要的车辆数更少,从而降低配送成本的问题,分析了需求可拆分的车辆路径问题的解的特征,证明了客户需求不宜拆分应满足的条件,设计了符合解的特征的聚类算法,并对其求解.通过实验仿真,将所提出的聚类算法与蚁群算法和禁忌搜索算法进行比较,所得结果表明了所提出的算法可以更有效地求得需求可拆分车辆路径问题的优化解,是解决需求可拆分车辆路径问题的有效方法.     

A two-phase metaheuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem, which aims to minimize the total arrival time at customers, is a relatively new variant of vehicle routing problem. It can be used to model many real-world applications, e.g., the important application arisen from the humanitarian aid after a natural disaster. In this paper, an approach, called two-phase metaheuristic, is proposed to deal with this problem. This algorithm starts from a solution. At each iteration, two interdependent phases use different perturbation and local search operators for solution improvement. The effectiveness of the proposed algorithm is empirically investigated. The comparison results show that the proposed algorithm is promising. Moreover, for nine benchmark instances, the two-phase metaheuristic can find better solutions than those reported in the previous literature.     

A planning model and solution algorithm for multi-trip split-delivery vehicle routing and scheduling problems with time windows

This study proposes a daily vehicle routing model for minimizing the total cost of replenishing inventory within a supply chain. The first major contribution of this research is to allow multiple use of vehicles in a split delivery vehicle routing problem with time windows (SDVRPTW), which is more realistic for various real-life applications. The multi-trip SDVRPTW (MTSDVRPTW) is formulated using the time–space network technique, which provides greater flexibility for formulating the complicated interactions between vehicles and products when multi-trip, split delivery, and delivery time windows are simultaneously considered. The resulting formulation of the MTSDVRPTW can be categorized as an integer multi-commodity network flow problem with side constraints. A two-step solution algorithm is proposed to solve this NP-hard problem, which is the second major contribution of this research. Finally, a real-world scale numerical example is performed to demonstrate and to test the methodology. The results indicate that these vehicle routing problems can be solved effectively and efficiently and that the proposed methodology has great potential for inventory replenishment scheduling where split deliveries and multiple trips for a single vehicle are allowed and time window constraints are imposed.     

A general heuristic for vehicle routing problems

We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (MDVRP), the site-dependent vehicle routing problem (SDVRP) and the open vehicle routing problem (OVRP).     

求解车辆路径问题的人工蜂群算法

采用人工蜂群算法对车辆路径问题进行求解,给出食物源的自然数编码方法,并采用邻域倒位方法生成候选食物源。应用算法求解了多个车辆路径问题的实例,并将结果与其它一些启发式算法进行了比较和分析。计算结果表明,人工蜂群算法可以有效求解车辆路径问题,同时也为算法求解其它一些组合优化问题提供了有益思路。     

基于种群多样性的自适应PSO算法求解VRPSPD问题

为有效求解逆向物流车辆路径(VRPSPD)模型,本文提出一种基于种群多样性的自适应PSO算法(SDAPSO)。在SDAPSO运行时,根据种群多样性,自适应地对种群中运行较差的粒子进行扰动操作,提升这些粒子向最优解收敛的能力;同时,对全局最优粒子进行概率扰动,以增加种群的多样性。标准检测函数的仿真结果表明SDAPSO算法是对基本PSO算法的有效改进。在对VRPSPD模型求解中,通过与其它粒子群算法相比,表明SDAPSO是求解该类问题的一种有效方法。     

A CONSTRAINT PROGRAMMING HEURISTIC FOR A HETEROGENEOUS VEHICLE ROUTING PROBLEM WITH SPLIT DELIVERIES

This article considers fresh goods distribution of a retail chain store in Turkey. The problem is formulated as a vehicle routing problem with a heterogeneous fleet for which no exact algorithm has ever been designed to solve it. A fast and effective algorithm based on constraint programming is proposed for the solution. The procedure is tested on some of the benchmark problems in literature. The real-life case is first solved assuming that delivery of a customer cannot be split between vehicles. Then it is resolved considering split deliveries. Solutions of both strategies are compared with the current performance of the firm to determine a distribution strategy. Results indicate considerable improvement in the performance of the firm.     

An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem

In this paper, an enhanced ant colony optimization (EACO) is proposed for capacitated vehicle routing problem. The capacitated vehicle routing problem is to service customers with known demands by a homogeneous fleet of fixed capacity vehicles starting from a depot. It plays a major role in the field of logistics and belongs to NP-hard problems. Therefore, it is difficult to solve the capacitated vehicle routing problem directly when solutions increase exponentially with the number of serviced customers. The framework of this paper is to develop an enhanced ant colony optimization for the capacitated vehicle routing problem. It takes the advantages of simulated annealing and ant colony optimization for solving the capacitated vehicle routing problem. In the proposed algorithm, simulated annealing provides a good initial solution for ant colony optimization. Furthermore, an information gain based ant colony optimization is used to ameliorate the search performance. Computational results show that the proposed algorithm is superior to original ant colony optimization and simulated annealing separately reported on fourteen small-scale instances and twenty large-scale instances.     

一种求解两级车辆路径问题的Memetic 算法

两级车辆路径问题是指物资必须先由中心仓库配送至中转站(第1级),再由中转站配送至客户(第2级)的一种车辆路径问题。针对该NP难问题提出一种Memetic算法通过自底向上的方式进行求解。首先利用改进的最优切割算法MDVRP-Split将客户合理分配至中转站;然后采用局部搜索解决第1级问题,交叉产生的精英个体通过局部搜索改进。标准算例的测试结果表明,所提出算法更注重求解质量与求解效率的平衡,性能优于其他现有的两种算法。     

A clonal selection algorithm for urban bus vehicle scheduling

The bus vehicle scheduling problem addresses the task of assigning vehicles to cover the trips in a timetable. In this paper, a clonal selection algorithm based vehicle scheduling approach is proposed to quickly generate satisfactory solutions for large-scale bus scheduling problems. Firstly, a set of vehicle blocks (consecutive trips by one bus) is generated based on the maximal wait time between any two adjacent trips. Then a subset of blocks is constructed by the clonal selection algorithm to produce an initial vehicle scheduling solution. Finally, two heuristics adjust the departure times of vehicles to further improve the solution. The proposed approach is evaluated using a real-world vehicle scheduling problem from the bus company of Nanjing, China. Experimental results show that the proposed approach can generate satisfactory scheduling solutions within 1 min.     

A hybrid particle swarm optimization algorithm for the vehicle routing problem

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for successfully solving one of the most popular supply chain management problems, the vehicle routing problem. The vehicle routing problem is considered one of the most well studied problems in operations research. The proposed algorithm for the solution of the vehicle routing problem, the hybrid particle swarm optimization (HybPSO), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search–greedy randomized adaptive search procedure (MPNS–GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is suitable for solving very large-scale vehicle routing problems as well as other, more difficult combinatorial optimization problems, within short computational time. It is tested on a set of benchmark instances and produced very satisfactory results. The algorithm is ranked in the fifth place among the 39 most known and effective algorithms in the literature and in the first place among all nature inspired methods that have ever been used for this set of instances.     

A generic framework for multi-criteria decision support in eco-friendly urban logistics systems

In this paper, we present a multi-objective shortest path evolutionary algorithm for comprehensive solutions to real-world manifestations of the classical vehicle routing problem. The shift from being a purely academic pursuit is highlighted by the introduction of a generic optimization framework which accommodates a variety of attributes that commonly occur in industrial applications. Specifically, the paper's main contribution are as follows: (1) consideration for the following real-world constraints: (a) time windows at customer locations, (b) simultaneous pickup and delivery demands, (c) a heterogeneous fleet of vehicles, and (d) the heterogeneity of traffic congestion levels in urban transportation networks; (2) assimilation of all the above attributes into a multi-objective program which aims to minimize environmental impact, while simultaneously addressing the overall operational costs of the routing solution and service quality concerns; a feat that has not been fully realized by known intelligent systems according to the authors’ best knowledge. In order to showcase the efficacy of the proposed algorithm, it is first tested on existing benchmark instances and then applied on a pair of real-world industrial examples from Singapore. These industrial examples serve as a source of new benchmarks which facilitate the study of different routing constraints and their effects on the economic and environmental viability of urban logistics systems.     

有时间窗的开放式车辆路径问题及其遗传算法

针对物流配送中的开放式车辆路径问题提出了OVRP的处理方法,并且根据容量和时间窗约束的特点设计了GA算法,设计了动态染色体,采用改进的交叉变异过程,利用随机参数的波动来协调容量约束和时间窗约束,并且加入了内部和外部扰动操作来跳出局部收敛点。通过试验,表明用GA在优化有容量和时间窗约束的OVRP的有效性。     

Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery

The location routing problem with simultaneous pickup and delivery (LRPSPD) is a new variant of the location routing problem (LRP). The objective of LRPSPD is to minimize the total cost of a distribution system including vehicle traveling cost, depot opening cost, and vehicle fixed cost by locating the depots and determining the vehicle routes to simultaneously satisfy the pickup and the delivery demands of each customer. LRPSPD is NP-hard since its special case, LRP, is NP-hard. Thus, this study proposes a multi-start simulated annealing (MSA) algorithm for solving LRPSPD which incorporates multi-start hill climbing strategy into simulated annealing framework. The MSA algorithm is tested on 360 benchmark instances to verify its performance. Results indicate that the multi-start strategy can significantly enhance the performance of traditional single-start simulated annealing algorithm. Our MSA algorithm is very effective in solving LRPSPD compared to existing solution approaches. It obtained 206 best solutions out of the 360 benchmark instances, including 126 new best solutions.     

A New Multi-objective Competitive Open Vehicle Routing Problem Solved by Particle Swarm Optimization

This paper presents a new variant of an open vehicle routing problem (OVRP), in which competition exists between distributors. In the OVRP with competitive time windows (OVRPCTW), the reaching time to customers affects the sales amount. Therefore, distributors intend to service customers earlier than rivals, to obtain the maximum sales. Moreover, a part of a driver??s benefit is related to the amount of sales; thus, the balance of goods carried in each vehicle is important in view of the limited vehicle capacities. In this paper, a new, multi-objective mathematical model of the homogeneous and competitive OVRP is presented, to minimize the travel cost of routes and to maximize the obtained sales while concurrently balancing the goods distributed among vehicles. This model is solved by the use of a multi-objective particle swarm optimization (MOPSO) algorithm, and the related results are compared with the results of NSGA-II, which is a well-known multi-objective evolutionary algorithm. A comparison of our results with three performance metrics confirms that the proposed MOPSO is an efficient algorithm for solving the competitive OVRP with a reasonable computational time and cost.     

A label based ant colony algorithm for heterogeneous vehicle routing with mixed backhaul

Vehicle heterogeneity and backhaul mixed-load problems are often studied separately in existing literature. This paper aims to solve a type of vehicle routing problem by simultaneously considering fleet heterogeneity, backhaul mixed-loads, and time windows. The goal is to determine the vehicle types, the fleet size, and the travel routes such that the total service cost is minimized. We propose a multi-attribute Label-based Ant Colony System (LACS) algorithm to tackle this complex optimization problem. The multi-attribute labeling technique enables us to characterize the customer demand, the vehicle states, and the route options. The features of the ant colony system include swarm intelligence and searching robustness. A variety of benchmark instances are used to demonstrate the computational advantage and the global optimality of the LACS algorithm. We also implemented the proposed algorithm in a real-world environment by solving an 84-node postal shuttle service problem for China Post Office in Guangzhou. The results show that a heterogeneous fleet is preferred to a homogenous fleet as it generates more cost savings under variable customer demands.