Solving the heterogeneous fixed fleet open vehicle routing problem by a combined metaheuristic algorithm

The vehicle routing problem (VRP) is a well-known combinatorial optimisation problem and holds a central place in logistics management. Many exact, heuristic and metaheuristic approaches have been proposed to solve VRP. An important variant of the VRP arises when a ?eet of vehicles is fixed and characterised by different capacities for distribution activities. The problem is known as the heterogeneous fixed fleet VRP (HFFVRP). The HFFVRP is a natural generalisation of the VRP with several vehicle types, each type being defined by a capacity, a fixed cost and a cost per distance unit, and can cover more practical situations in transportation. This problem consists of determining a set of vehicle trips of minimum total length in which a set of customers is to be satisfied in the demand constraints using identical vehicles with limited capacity. If open routes instead of closed ones are considered in the HFFVRP, the problem becomes a heterogeneous fixed fleet Open VRP (HFFOVRP) which has numerous applications in industrial and service problems. In this paper, a bone route algorithm which uses the tabu search as an improved procedure is utilised to solve the HFFOVRP. The proposed algorithm was tested empirically on a 24 of generated VRPs, and compared with elite ant system and ant colony system. In all cases, the proposed algorithm finds the best-known solutions within a reasonable time.     

考虑油耗的车辆调度问题模型与算法

针对目前运输行业中能源消耗已经成为影响社会环境和运行成本的重要因素这一实际,在分析汽车行驶油耗规律和定量描述的基础上,引入考虑能源消耗的车辆调度问题,考虑了车辆运行能耗目标以及客户的需求时间窗等约束,建立问题的精确数学模型。由于问题具有NP hard性质,为了求解实际大规模此类问题而设计了一种新型禁忌搜索算法。该算法引入大规模邻域搜索思想,并提出基于虚拟车辆的新型搜索邻域。通过算例试验验证了算法的有效性。     

A vehicle routing problem with time windows and stochastic demands

Abstract

This study presents an approach for considering a vehicle routing problem where customers’ pickup demands are uncertain and require serving within some settled time windows. Customers’ demands are assumed to follow given discrete probability distributions. This study proposes a nonlinear stochastic integer program with recourse to formulate the vehicle routing problem with stochastic demands and time windows (VRPTW‐SD, for short). The objective of the VRPTW‐SD is to minimize the total cost of the first‐stage solution and expected recourse cost of the second‐stage solution. The total cost of the first‐stage problem includes the total travel cost for all links and the total waiting cost at all nodes. When a vehicle capacity is attained or exceeded, recourse actions are needed and recourse costs incurred in order to finish the planned route schedules. Two categories of schedule failure are introduced in this work; the recourse costs derive from the variations in travel time travel time, waiting time, and penalties of late arrival for time windows. In addition, an optimization algorithm is developed for solving the VRPTW‐SD, according to the framework of the L‐shaped method. Numerical results are given to demonstrate its validity.     

面向快递同城运输的车辆路径问题研究

为降低运输成本,研究了快递同城运输中的车辆路径问题。建立多车型,含时间窗约束、容量约束、车辆限行约束,并考虑错峰交货的,以最小化运输成本为目标的混合整数规划模型。提出以点到点集的距离之和作为邻域搜索优先指标的构造性启发式算法,设计了基于“路径−车型对”的列生成算法,初始列由启发式算法求得。实验结果显示,对于120个点的大规模问题,列生成算法只需175秒就能得到近似最优解,验证了该算法的有效性及对一定规模内快递同城运输问题的适用性。     

A hybrid genetic algorithm for the multi-depot open vehicle routing problem

This paper studies the multi-depot open vehicle routing problem (MDOVRP), a variant of the vehicle routing problem (VRP), in which vehicles start from several depots and are not required to return to the depot. Despite the vast amount of literature about VRPs, the MDOVRP has received very little attention from researchers. In this paper, a new hybrid genetic algorithm is presented for finding the routes that minimize the traveling cost of the vehicles. Computational results on a number of test instances indicate the proposed algorithm dominates the CPLEX solver and the existing approach in the literature. Meanwhile, experiments are conducted on multi-depot VRP benchmarks, and the results are compared with a sophisticated tabu search approach and an exact method.     

基于遗传算法的共享助力车调度问题研究

为了减少调度运营成本,减少调度时间,研究共享助力车的调度问题。将助力车调度和电池配送统一进行,考虑载重对燃油调度车的油耗影响,以燃油调度车固定使用成本和耗油成本最小为目标函数,构建助力车重分配的调度模型。通过AP算法对大范围内的电子围栏进行区域划分,确定助力车的服务范围和调度中心选址的基础上,用遗传算法对各个区域分别求解最小成本的路径规划方案。用算例验证了本模型与算法的有效性和可行性。     

Optimisation of the multi-depots pick-up and delivery problems with time windows and multi-vehicles using PSO algorithm

Many sectors in the transport industry are concerned about the vehicle routing problem (VRP), hence the growing interest of researchers for this type of problem and its variants. This is due essentially to its many real applications in logistics for the transport of goods. The originality and contribution of our work is that we have dealt a problem that combines several variants: multiple vehicles (m), multiple depots (MD), pickup and delivery problem (PDP) with time windows (TW). Hence the notation of our problem: m-MDPDPTW. In this paper, we present the m-MDPDPTW, which is an optimisation problem belonging to the category of NP Hard problems. This problem must meet requests for transport between customers and suppliers satisfying precedence, capacity and time constraints. The goal is to find the best solution, which is the best route minimising the total travelled distance. To solve and optimise our m-MDPDPTW, we have developed a new algorithm based on the particle swarm optimisation (PSO) method. The performance of this new approach is tested on data set instances of Li and Lim's benchmark problems in which we have added multiple depot locations. Comparing with prior works, our proposed approach gave better results by decreasing the distance for several studied instances.     

改进分散搜索算法求解包装废弃物回收路径规划问题

目的 将包装废弃物回收路径规划归纳为一个带回路和时间窗的逆向物流车辆路径问题（RL-VRPBTW）,以最小化回收成本、发车成本和时间窗惩罚为联合优化目标进行建模。方法 引入“车辆剩余空间回收能力”因素,改进经典节约里程算法,求得较好的初始解;基于分散搜索框架,设计基于初始解改进的分散搜索算法（ISISS）,根据问题模型,采用含0的编码方式,通过多样性产生、参考集更新、子集产生、子集合并、解改进等5个步骤实现算法功能。结果 在“部分回收点分布较密集”的城市型地理场景下,针对快消企业的低值固废包装,生成回收点数量分别为50、100、200的3种规模算例,并考虑大小两种车型进行仿真实验。将ISISS算法与改进节约里程、遗传和分散搜索3种算法比较后可知,ISISS算法在大规模包装废弃物回收车辆路径问题上具有更优的求解性能。结论 仿真实验结果表明,ISISS是一种求解多目标大规模包装废弃物回收路径规划问题的较优算法。     

带软时间窗的同时取送货车辆路径问题研究

考虑软时间窗下的车辆路径问题,客户点常伴有同时取送货的双重需求。针对此类问题,通过对软时间窗、车辆在途前后时间关系及二者融合问题进行刻画,同时将车辆行驶距离、车辆使用数、违反软时间窗总时间、客户满意度等纳入综合考量,构建相应混合整数非线性规划(mixed integer nonlinear programming, MINLP)模型。设计相应多目标优化求解算法,运用理想点法对目标函数进行转化,将多目标优化问题转化为单目标优化问题。结合相应算例集,运用LINGO 17.0全局求解程序求得每组算例的全局最优解。结果表明,针对带软时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pick-up and delivery and soft time windows, VRPSPDSTW),所建模型及算法是有效且可行的。     

A memetic algorithm with iterated local search for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult vehicle routing problem, where given an undirected graph, the objective is to minimize the total cost of all vehicle tours that serve all required edges under vehicle capacity constraints. In this paper, a memetic algorithm with iterated local search (MAILS) is proposed to solve this problem. The proposed MAILS incorporates a new crossover operator, i.e., the longest common substring crossover (LCSX), an iterated local search (ILS) and a perturbation mechanism into the framework of the memetic algorithm (MA). The proposed MAILS is evaluated on the CARP benchmark instances and computational results show that the MAILS is very competitive.     

共享策略下甩挂车辆调度问题的分析及求解

目的为了克服现阶段下甩挂货运过程中存在的空载率高、牵引车利用率低等问题,从服务点间的货运关系出发,对货运单循环系统中共享策略下甩挂车辆调度问题进行设计研究。方法以牵引车行驶总里程为目标函数,构建共享策略下甩挂车辆调度模型,并基于模拟退火算法对其进行优化求解。结果以山东省的2家小型运输企业为案例进行了仿真分析,与普通车辆调度模式分析比较可知,共享策略下调度模式的空载率、单位货运成本、单位货运油耗、牵引车利用率分别优化了79.6%,50%,22.6%,171.4%。结论文中构建的共享策略下甩挂车辆调度模型及其求解算法可行有效,在减少空载行程、提高燃油利用率等方面具有良好的效果。     

An efficient method for dynamic-demand joint replenishment problem with multiple suppliers and multiple vehicles

How to improve competitive edges to meet rapidly changing market environment and dynamic customer needs is critical for the survival and success of firms these days. A good supply chain and inventory management is a necessity in the intensive competitive market. This paper considers a dynamic-demand joint replenishment problem with multiple vehicle routing. The problem is first formulated as a mixed integer programming model with an objective to minimise total costs, which include ordering cost, purchase cost, production cost, transportation cost and holding cost, under a prerequisite that inventory shortage is prohibited in the system. A particle swarm optimisation model is proposed next to solve large-scale problems which are computationally difficult. A case study of a touch panel manufacturer is presented to examine the practicality of the models.     

A review on the electric vehicle routing problems: Variants and algorithms

Over the past decade, electric vehicles (EVs) have been considered in a growing number of models and methods for vehicle routing problems (VRPs). This study presents a comprehensive survey of EV routing problems and their many variants. We only consider the problems in which each vehicle may visit multiple vertices and be recharged during the trip. The related literature can be roughly divided into nine classes: Electric traveling salesman problem, green VRP, electric VRP, mixed electric VRP, electric location routing problem, hybrid electric VRP, electric dial-a-ride problem, electric two-echelon VRP, and electric pickup and delivery problem. For each of these nine classes, we focus on reviewing the settings of problem variants and the algorithms used to obtain their solutions.     

应用蜜蜂繁殖进化型粒子群算法求解车辆路径问题

为了提高粒子群算法求解车辆路径问题时收敛速度和全局搜索能力,将蜜蜂繁殖进化机制与粒子群算法相结合,应用到CVRP问题的求解。该算法中,最优的个体作为蜂王与通过选择机制选择的雄蜂以随机概率进行交叉,增强了最优个体信息的应用能力;同时,随机产生一部分雄蜂种群,并将其与蜂王交叉增加了算法的多样性。实例分析表明该算法具有较好的全局搜索能力,验证了该算法的可行性。     

分割配送的生鲜产品库存-路径优化研究

目的 基于供应商管理库存策略,优化协调第三方物流（3rd Party Logistics,3PL）参与的二级供应链系统中库存补充与补货配送的关系,在满足配送需求的同时降低系统的库存和运输成本。方法 综合考虑3PL物流模式下的库存-路径系统中生鲜产品的运输距离、质量时间窗以及需求分割配送策略在时间上的调整等因素,以异质车队车辆行驶燃油成本、车辆调用固定成本、配送超时腐坏成本以及各零售商的库存成本为目标函数,建立多品种生鲜产品库存-路径优化模型。结果 通过改进的遗传算法计算并进行配送量调整优化,得到最终的生鲜配送方案,其系统总成本比配送量调整前减少了9.98%。结论 通过在时间上对配送量进行拆分调整可以有效地节约供应链系统总成本。     

An integrated optimal inventory lot-sizing and vehicle-routing model for a multisupplier single-assembler system with JIT delivery

In a manufacturing system, a just-in-time (JIT) procurement and supply system is important for reducing cost and responding to customer’s requirement quickly. Successful implementation of a JIT system needs supplier/manufacturer cooperation in small lot-size delivery and inbound logistics cost reduction. In this study, an integrated optimal model of inventory lot-sizing vehicle routing of multisupplier single-manufacturer with milk-run JIT delivery is established. A novel method for computing transportation cost is proposed. Because the integrated model is a NP-hard problem, a meta-heuristic algorithm of ant colony optimisation is developed for solving the model. Numerical examples are used to demonstrate and test the effectiveness of the model and the algorithm. The results show that integrated model with milk-run delivery can reduce the total cost and realise the JIT production and procurement philosophy which emphasises small lot-size production and delivery. The results highlight the importance of cooperation between suppliers and manufacturers in JIT production practices.     

A two-stage decomposition method on fresh product distribution problem

Refrigerator cars are widely used for fresh product distribution. The energy consumption of these vehicles is sensitive to the environment temperature, and changes continuously due to fluctuations of the environment temperature. As a result, the total refrigeration cost is influenced by the car’s departure time. To reduce operation costs of third-party transportation providers, the refrigerator car scheduling problem is addressed in this research. A time-dependent mixed-integer programming model is established to reduce total operation costs, including routing, time penalty, cargo damage and refrigeration costs. An adaptive heuristic method is proposed by combining the variable neighbourhood search and particle swarm optimisation. To improve the algorithm quality, a two-stage decomposition method is developed. The problem is divided into two echelon sub-problems. One is the shortest path problem, and the other is the departure time scheduling problem. A feedback strategy is utilised to avoid local optimal solutions and design of experiments methodology is adopted to derive the optimal parameter setting of the algorithm. Numerical experiments are conducted to demonstrate the effectiveness of the proposed time-dependent decision model.     

Harmony search optimization algorithm for a novel transportation problem in a consolidation network

This article presents a new harmony search optimization algorithm to solve a novel integer programming model developed for a consolidation network. In this network, a set of vehicles is used to transport goods from suppliers to their corresponding customers via two transportation systems: direct shipment and milk run logistics. The objective of this problem is to minimize the total shipping cost in the network, so it tries to reduce the number of required vehicles using an efficient vehicle routing strategy in the solution approach. Solving several numerical examples confirms that the proposed solution approach based on the harmony search algorithm performs much better than CPLEX in reducing both the shipping cost in the network and computational time requirement, especially for realistic size problem instances.     

Transient stability constrained optimal power flow using particle swarm optimisation

A novel approach based on the particle swarm optimisation (PSO) technique is proposed for the transient-stability constrained optimal power flow (TSCOPF) problem. Optimal power flow (OPF) with transient-stability constraints considered is formulated as an extended OPF with additional rotor angle inequality constraints. For this nonlinear optimisation problem, the objective function is defined as minimising the total fuel cost of the system. The proposed PSO-based approach is demonstrated and compared with conventional OPF as well as a genetic algorithm based counterpart on the IEEE 30-bus system. Furthermore, the effectiveness of the PSO-based TSCOPF in handling multiple contingencies is illustrated using the New England 39-bus system. Test results show that the proposed approach is capable of obtaining higher quality solutions efficiently in the TSCOPF problem     

An optimization algorithm for a capacitated vehicle routing problem with time windows

In this paper, vehicle routing problem (VRP) with time windows and real world constraints are considered as a real-world application on google maps. Also, tabu search is used and Hopfield neural networks is utilized. Basic constraints consist of customer demands, time windows, vehicle speed, vehicle capacity and working hours. Recently, cost and on-time delivery are the most important factors in logistics. Thus, the logistic applications attract attention of companies. In logistic management, determining the locations of delivery points and deciding the path are the vital components that should be considered. Deciding the paths of vehicles provides companies to use their vehicles efficiently. And with utilizing optimized paths, big amounts of cost and time savings will be gained. The main aim of the work is providing the best path according to the needs of the customers, minimizing the costs with utilizing the VRP and presenting an application for companies that need logistic management. To compare the results, simulated annealing is used on special scenarios. And t-test is performed in the study for the visited path in km with p-value of 0.05.