多约束选址—路径问题的改进混合遗传算法研究

选址—路径问题(LRP)同时解决设施选址和车辆路径问题,使物流系统总成本达到最小,在集成化物流配送网络规划中具有重要意义。针对带仓库容量约束和路径容量约束的选址—路径(CLRP)问题,提出了一种结合模拟退火算法的混合遗传算法进行整体求解。改进混合遗传算法分别对初始种群生成方式、遗传操作和重组策略进行改进,并实现了模拟退火的良好局部搜索能力与遗传算法的全局搜索能力的有效结合。运用一组Barreto Benchmark算例进行数值实验测试其性能,并将求解结果与国外文献中的启发式算法进行比较,验证了改进混合算法的有效性和可行性。     

A Branch-and-Cut method for the Capacitated Location-Routing Problem

Recent researches in the design of logistic networks have shown that the overall distribution cost may be excessive if routing decisions are ignored when locating depots. The Location-Routing Problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. The aim of this paper is to propose an exact approach based on a Branch-and-Cut algorithm for solving the LRP with capacity constraints on depots and vehicles. The proposed method is based on a zero-one linear model strengthened by new families of valid inequalities. The computational evaluation on three sets of instances (34 instances in total), with 5–10 potential depots and 20–88 customers, shows that 26 instances with five depots are solved to optimality, including all instances with up to 40 customers and three with 50 customers.     

A GRASP×ELS approach for the capacitated location-routing problem

This paper addresses the capacitated location-routing problem (CLRP), raised by distribution networks involving depot location, fleet assignment and routing decisions. The CLRP is defined by a set of potential depot locations, with opening costs and limited capacities, a homogeneous fleet of vehicles, and a set of customers with known demands. The objective is to open a subset of depots, to assign customers to these depots and to design vehicle routes, in order to minimize both the cost of open depots and the total cost of the routes. The proposed solution method is a greedy randomized adaptive search procedure (GRASP), calling an evolutionary local search (ELS) and searching within two solution spaces: giant tours without trip delimiters and true CLRP solutions. Giant tours are evaluated via a splitting procedure that minimizes the total cost subject to vehicle capacity, fleet size and depot capacities. This framework is benchmarked on classical instances. Numerical experiments show that the approach outperforms all previously published methods and provides numerous new best solutions.     

A genetic algorithm approach for location-inventory-routing problem with perishable products

In this paper, we address a location-inventory-routing model for perishable products. The model determines the number and location of required warehouses, the inventory level at each retailer, and the routes traveled by each vehicle. The proposed model adds location decisions to a recently published inventory routing problem in order to make it more practical, thus supporting the prevalent claim that integration of strategic, tactical and operational level decisions produces better results for supply chains. Given that the model developed here is NP-hard, with no algorithm capable of finding its solution in polynomial time, we develop a Genetic Algorithm approach to solve the problem efficiently. This approach achieves high quality near-optimal solutions in reasonable time. Furthermore, the unique structure of the problem requires developing a new chromosome representation, as well as local search heuristics. Finally, an analysis is carried out to verify the effectiveness of the algorithm.     

Multi-depot vehicle routing problem: a one-stage approach

This paper introduces multi-depot vehicle routing problem with fixed distribution of vehicles (MDVRPFD) which is one important and useful variant of the traditional multi-depot vehicle routing problem (MDVRP) in the supply chain management and transportation studies. After modeling the MDVRPFD as a binary programming problem, we propose two solution methodologies: two-stage and one-stage approaches. The two-stage approach decomposes the MDVRPFD into two independent subproblems, assignment and routing, and solves them separately. In contrast, the one-stage approach integrates the assignment with the routing where there are two kinds of routing methods-draft routing and detail routing. Experimental results show that our new one-stage algorithm outperforms the published methods. Note to Practitioners-This work is based on several consultancy work that we have done for transportation companies in Hong Kong. The multi-depot vehicle routing problem (MDVRP) is one of the core optimization problems in transportation, logistics, and supply chain management, which minimizes the total travel distance (the major factor of total transportation cost) among a number of given depots. However, in real practice, the MDVRP is not reliable because of the assumption that there have unlimited number of vehicles available in each depot. In this paper, we propose a new useful variant of the MDVRP, namely multi-depot vehicle routing problem with fixed distribution of vehicles (MDVRPFD), to model the practicable cases in applications. Two-stage and one-stage solution algorithms are also proposed. The industry participators can apply our new one-stage algorithm to solve the MDVRPFD directly and efficiently. Moreover, our one-stage solution framework allows users to smoothly add new specified constraints or variants.     

A hybrid simulated annealing algorithm for location and routing scheduling problems with cross-docking in the supply chain

The location and routing scheduling problems with cross-docking can be regarded as new research directions for distribution networks in the supply chain. The aims of these problems are to concurrently design a cross-docking center location and a vehicle routing scheduling model, known as NP-hard problems. This paper presents a two-stage mixed-integer programming (MIP) model for the location of cross-docking centers and vehicle routing scheduling problems with cross-docking due to potential applications in the distribution networks. Then, a new algorithm based on a two-stage hybrid simulated annealing (HSA) with a tabu list taken from tabu search (TS) is proposed to solve the presented model. This proposed HSA not only prevents revisiting the solution but also maintains the stochastic nature. Finally, small and large-scale test problems are randomly generated and solved by the HSA algorithm. The computational results for different problems show that the proposed HSA performs well and converges fast to reasonable solutions.     

Incorporating lateral transfers of vehicles and inventory into an integrated replenishment and routing plan for a three-echelon supply chain

This paper focuses on developing an integrated replenishment and routing plan that takes into account lateral transfers of both vehicles and inventory for a three-echelon supply chain system including a single plant, multiple distribution centers and multiple retailers. A mixed integer programming model to the overall system is formulated first, and then an optimization-based heuristic consisting of three major components is proposed. The purpose of the first component is to assign retailers to distribution centers, and determine routing schedules for each distribution center. And the remaining two components are corresponding to two smaller optimization models – a variant of the classical transportation problem modeled for determining vehicle transfer between distribution centers, and a variant of the conventional minimum cost network flow problem modeled for determining inventory replenishment and transfer. Experimental results reveal that the proposed algorithm is rather computational effectiveness, and the pooling strategy that considers both vehicles and inventory transfers is a worthy option in designing supply chain operations.     

多配送中心下生鲜农产品同步取送选址-路径优化

多配送中心下生鲜农产品配送工作中配送中心选址和车辆取送是两项最为重要的工作，故本文研究带同步取送的生鲜农产品选址?路径问题。首先，建立考虑车辆容量、货物作业时间、取送作业时间窗等约束条件的非线性规划模型，模型以各配送区域内产生的运输成本、惩罚费用、货损费用总和最小为目标函数。然后，根据模型特点设计融合中心评估指数和改进遗传算法的启发式算法，算法先利用中心评估指数确定配送中心和车辆的配送区域，将区域划分的信息传递给改进遗传算法进行各区域内的路径优化。最后，通过对比取送分离和同步取送两种配送方式验证本文提出的配送模式及模型是合理有效的，可为企业的生鲜农产品配送提供决策依据。     

A new approach on auxiliary vehicle assignment in capacitated location routing problem

The location routing problem (LRP) considers locating depots and vehicle routing decisions simultaneously. In classic LRP the number of customers in each route depends on the capacity of the vehicle. In this paper a capacitated LRP model with auxiliary vehicle assignment is presented in which the length of each route is not restricted by main vehicle capacity. Two kinds of vehicles are considered: main vehicles with higher capacity and fixed cost and auxiliary vehicles with lower capacity and fixed cost. The auxiliary vehicles can be added to the transportation system as an alternative strategy to cover the capacity limitations and they are just used to transfer goods from depots to vehicles and cannot serve the customers by themselves. To show the applicability of the proposed model, some numerical examples derived from the well-known instances are used. Moreover the model has been solved by some meta-heuristics for large sized instances. The results show the efficiency of the proposed model and the solution approach, considering the classic model and the exact solution approach, respectively.     

基于遗传算法的应用层多播路由方案

通过分析应用层多播树的路由约束,定义了3个适值函数,分别考察应用层多播树在开销、平衡和网络层业务量均衡3方面的性能。并根据生成的总适值函数进行遗传算法操作．仿真结果表明,与基于几何规则的应用层路由算法比较,本文提出的算法对多播树的3方面性能都有所优化,树的平衡和网络层业务量均衡性能的优化程度尤为明显．     

Designing tributary networks with multiple ring families

Advances in telecommunication technology result in improved service, but can also lead to difficult and challenging network design problems. For example, networks in which nodes are connected by rings of optical fiber can now be used to provide rapid service restoration in the event of a failure. However, as a result, network designers are faced with the new problem of designing networks based on topological ring structures. In this paper, we consider the particular case of tributary network design. In a tributary network, a group of nodes are connected to a hub node, which is used as a point of interconnection with other parts of the network. For a particular network architecture, we describe an algorithm to determine how many topological ring structures are required, and which nodes should be included on each. We highlight connections between this problem and problems in vehicle routing.A common architecture for a telecommunications network consists of several tributary (often called access) networks, which connect locations to hubs, and a backbone network, which interconnects the hubs. This paper describes a heuristic approach for designing tributary networks based on self-healing rings (SHRs). The tributary network consists of multiple ring families, and each of those is comprised of one or more SHRs, called “stacked” rings. The SHRs in a given ring family are routed over the same cycle of optical fiber cables, but each SHR serves only a subset of the locations along the cycle. Each demand location is assigned to a single SHR on one of the ring families, whereas the hub is assigned to all SHRs on all ring families. A link that is used by some ring family incurs a fixed cost plus a variable cost per SHR associated with that family. Each SHR is constrained by the demand volume it can handle and by the number of locations it can serve. This tributary ring network design problem can be viewed as a complex version of a vehicle routing problem with a single-depot andmultiple vehicles. Our algorithm is initiated with numerous ring families. It then attempts to merge these families, while ensuring that savings are realized in terms of the sum of fixed and variable costs.     

Design and performance analysis of an inductive QoS routing algorithm

Routing mechanism is key to the success of large-scale, distributed communication and heterogeneous networks. Consequently, computing constrained shortest paths is fundamental to some important network functions such as QoS routing and traffic engineering. The problem of QoS routing with multiple additive constraints is known to be NP-complete but researchers have been designing heuristics and approximation algorithms for multi-constrained paths algorithms to propose pseudo-polynomial time algorithms. This paper introduces a polynomial time approximation quality of service (QoS) routing algorithm and constructs dynamic state-dependent routing policies. The proposed algorithm uses an inductive approach based on trial/error paradigm combined with swarm adaptive approaches to optimize lexicographically various QoS criteria. The originality of our approach is based on the fact that our system is capable to take into account the dynamics of the network where no model of the network dynamics is assumed initially. Our approach samples, estimates, and builds the model of pertinent aspects of the environment which is very important in heterogeneous networks. The algorithm uses a model that combines both a stochastic planned pre-navigation for the exploration phase and a deterministic approach for the backward phase. Multiple paths are searched in parallel to find the K best qualified ones. To improve the overall network performance, a load adaptive balancing policy is defined and depends on a dynamic traffic path probability distribution function. We conducted a performance analysis of the proposed QoS routing algorithm using OPNET based on a platform simulated network. The obtained results demonstrate substantial performance improvements as well as the benefits of learning approaches over networks with dynamically changing traffic.     

基于时空聚类求解带容积约束的选址-路径问题

选址-路径问题是供应链管理和物流系统规划中的一个重要问题,对总成本具有十分重要的影响.对考虑配送中心容积约束的带时间窗的选址-路径问题进行研究,建立以总成本最小和客户满意度最大为目标的多目标规划模型,提出两阶段算法对其进行求解.首先,利用k-means聚类算法确定配送中心选址;然后,提出一种基于时间-空间双因素的客户划分方法以确定配送中心所服务客户;最后,利用粒子群算法对各配送中心的配送路径进行规划.数值算例表明,所提出的算法较其他已有算法,均能有效地降低物流运作总成本及总配送路径长度,为解决带容积约束及时间窗的选址-路径问题提供了一种新的解决思路.     

基于神经网络的动态路由选择算法

在分析了网络中基于QoS组播路由问题的基础上,文章给出了基于Hopfield神经网络的动态路由选择算法的模型。仿真研究表明该算法具有良好的分布特性和智能决策能力,此方案不仅保证了带宽、端到端延时和延时抖动,优化了路由树的代价,而且有效地控制了算法的复杂性,是一种快速动态组播路由算法,能实现全局网络资源利用的优化,容易扩展到大型网络中应用。     

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.     

不确定环境下多品类共同配送路径优化

针对动态事件对配送过程的干扰问题，提出多品类共同配送车辆路径优化问题。基于对不确定环境下动态客户时空特性的分析，提出利用时空泊松分布生成动态客户的方法；并从整体运营成本及车辆固定成本入手，建立不确定环境下多品类共同配送模型；鉴于考虑模型的特殊性，设计遗传-禁忌搜索组合优化算法，结合具体算例对模型和算法性能进行验证。结果表明，提出的多品类共同配送方法优于单品类配送方法，且改进后的遗传-禁忌搜索算法具有更强的寻优能力。     

The inventory-routing problem with transshipment

This paper introduces the Inventory-Routing Problem with Transshipment (IRPT). This problem arises when vehicle routing and inventory decisions must be made simultaneously, which is typically the case in vendor-managed inventory systems. Heuristics and exact algorithms have already been proposed for the Inventory-Routing Problem (IRP), but these algorithms ignore the possibility of performing transshipments between customers so as to further reduce the overall cost. We present a formulation that allows transshipments, either from the supplier to customers or between customers. We also propose an adaptive large neighborhood search heuristic to solve the problem. This heuristic manipulates vehicle routes while the remaining problem of determining delivery quantities and transshipment moves is solved through a network flow algorithm. Our approach can solve four different variants of the problem: the IRP and the IRPT, under maximum level and order-up-to level policies. We perform an extensive assessment of the performance of our heuristic.     

A new integrated mathematical model for a bi-objective multi-depot location-routing problem solved by a multi-objective scatter search algorithm

The location of manufacturing facilities is one of the most important strategic decisions considered in the design of logistic systems. Another important strategic decision is the structure and management of the fleets. Most often, even if two types of problem (i.e., location of facilities and vehicle routing) have occurred in a given scenario, they have been studied and solved separately. This paper presents a new integrated mathematical model for a bi-objective multi-depot location-routing problem where the total demand served is to be maximized and the total cost, consisting of start-up of the facility, fixed and variable depots and variable delivery cost, is to be minimized. Since this type of the problem is NP-hard, a new multi-objective scatter search (MOSS) algorithm is proposed to obtain the Pareto frontier for the given problem. To validate the performance of the proposed MOSS algorithm in terms of the solution quality and diversity level, various test problems are carried out and the efficiency of this algorithm based on some comparison metrics is compared with the elite tabu search (ETS). The computational results show that the proposed MOSS outperforms the ETS, especially in large-sized problems.     

A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries

The vehicle routing problem with simultaneous pick-up and deliveries, which considers simultaneous distribution and collection of goods to/from customers, is an extension of the capacitated vehicle routing problem. There are various real cases, where fleet of vehicles originated in a depot serves customers with pick-up and deliveries from/to their locations. Increasing importance of reverse logistics activities make it necessary to determine efficient and effective vehicle routes for simultaneous pick-up and delivery activities. The vehicle routing problem with simultaneous pick-up and deliveries is also NP-hard as a capacitated vehicle routing problem and this study proposes a genetic algorithm based approach to this problem. Computational example is presented with parameter settings in order to illustrate the proposed approach. Moreover, performance of the proposed approach is evaluated by solving several test problems.     

求解动态需求车辆调度问题的自适应量子遗传算法

针对物流配送过程中存在的动态车辆调度问题,即带载车量约束的实时优化车辆路径问题,提出一种自适应量子遗传算法,用于最小化配送成本.根据搜索点目标函数的变化率,提出一种自适应量子旋转门更新方式,并通过子种群适应度值的变化确定量子旋转角的方向和大小,进而引导种群进化方向,提高算法的全局搜索广泛性;设计了一种变异操作,用于保持自适应量子遗传算法的种群多样性,进而提高算法全局搜索的宽泛性;引入基于两元素搜索原则的局部搜索方法来增强算法的局部优化能力.仿真实验和算法比较验证了所提算法的有效性和优越性.