定位2运输路线安排问题的两阶段启发式算法

重点研究了集成化物流中一类特殊的定位一运输路线安排问题(LRP)的解决方法．LRP问题包括设施定位和运输路线优化两方面决策，属于NP-hard难题．由于问题的复杂性，提出基于假设前提的LRP模型及其两阶段启发式求解算法．该方法分两步实现：首先，采用基于最小包络聚类分析的启发式方法确定被选择的潜在设施及由每一个选中的设施所要提供服务的客户群；其次，运用带有控制开关的遗传算法求解每一确定客户类中的优化运输路线．提出利用两阶段启发式算法求解LRP问题，此方法实现容易、运算简单，一定程度上避免了遗传算法中的“局部最优现象”．仿真实验证明了该算法求解单目标LRP的有效性和准确性．     

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 two-phase hybrid heuristic algorithm for the capacitated location-routing problem

In this paper, we propose a two-phase hybrid heuristic algorithm to solve the capacitated location-routing problem (CLRP). The CLRP combines depot location and routing decisions. We are given on input a set of identical vehicles (each having a capacity and a fixed cost), a set of depots with restricted capacities and opening costs, and a set of customers with deterministic demands. The problem consists of determining the depots to be opened, the customers and the vehicles to be assigned to each open depot, and the routes to be performed to fulfill the demand of the customers. The objective is to minimize the sum of the costs of the open depots, of the fixed cost associated with the used vehicles, and of the variable traveling costs related to the performed routes. In the proposed hybrid heuristic algorithm, after a Construction phase (first phase), a modified granular tabu search, with different diversification strategies, is applied during the Improvement phase (second phase). In addition, a random perturbation procedure is considered to avoid that the algorithm remains in a local optimum for a given number of iterations. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several solutions obtained by the previously published methods and new best known solutions.     

基于最大最小蚂蚁系统的动态车辆路径问题研究

在描述动态车辆路径问题的基础上,通过对计划周期分片,将动态车辆路径问题转换为一系列的静态子问题,并采用改进的最大最小蚂蚁系统对静态子问题进行求解。在最大最小蚂蚁系统中,针对聚类分布和随机分布的客户,分别采用顺序法和并行法构建路线,信息素的更新量随着可选客户数量的不同而改变,同时在算法执行过程中对期望启发式因子、选择概率、信息素持续因子和蚂蚁数量等参数进行自适应调整。以整个路线的行驶距离作为目标,采用该算法对9个算例进行测试,与其他文献中算法的计算结果相比较,在使用车辆数量基本一致的情况下,9个问题都得到了最好解和最好平均解,表明了算法的有效性。     

Skewed general variable neighborhood search for the location routing scheduling problem

The integrated location routing scheduling problem is a variant of the well-known location routing problem. The location routing problem consists in selecting a set of depots to open and in building a set of routes from these depots, to serve a set of customers at minimum cost. In this variant, a vehicle can perform more than a single route in the planning period. As a consequence, the routes have to be scheduled within the workdays of each vehicle. The problem arises typically when routes are constrained to have a short duration. It happens for example within the boundaries of small geographic areas or in the transportation of perishable goods. In this paper, we propose a skewed general variable neighborhood search based heuristic to solve it. The algorithm is tested extensively and we show that it is efficient and provides the proven optimal solution in a significant number of cases. Moreover, it clearly outperforms a multi-start VND based heuristic that uses the same neighborhood structures.     

A decomposition-based heuristic for the multiple-product inventory-routing problem

The inventory-routing problem is an integrated logistics planning problem arising in situations where customers transfer the responsibility for inventory replenishment to the vendor. The vendor must then decide when to visit each customer, how much to deliver and how to sequence customers in vehicle routes. In this paper, we focus on the case where several different products have to be delivered by a fleet of vehicles over a finite and discrete planning horizon. We present a three-phase heuristic based on a decomposition of the decision process of the vendor. In the first phase, replenishment plans are determined by using a Lagrangian-based method. These plans do not specify delivery sequences for the vehicles. The sequencing of the planned deliveries is performed in the second phase in which a simple procedure is employed to construct vehicle routes. The third phase incorporates planning and routing decisions into a mixed-integer linear programming model aimed at finding a good solution to the integrated problem. Computational experiments show that our heuristic is effective on instances with up to 50 customers and 5 products.     

Agile optimization of a two‐echelon vehicle routing problem with pickup and delivery

In this paper, we consider a vehicle routing problem in which a fleet of homogeneous vehicles, initially located at a depot, has to satisfy customers' demands in a two‐echelon network: first, the vehicles have to visit intermediate nodes (e.g., a retail center or a consolidation center), where they deliver raw materials or bulk products and collect a number of processed items requested by the customers in their route; then, the vehicles proceed to complete their assigned routes, thus delivering the processed items to the final customers before returning to the depot. During this stage, vehicles might visit other intermediate nodes for reloading new items. In some real‐life scenarios, this problem needs to be solved in just a few seconds or even milliseconds, which leads to the concept of “agile optimization.” This might be the case in some rescue operations using drones in humanitarian logistics, where every second can be decisive to save lives. In order to deal with this real‐time two‐echelon vehicle routing problem with pickup and delivery, an original constructive heuristic is proposed. This heuristic is able to provide a feasible and reasonably good solution in just a few milliseconds. The constructive heuristic is extended into a biased‐randomized algorithm using a skewed probability distribution to modify its greedy behavior. This way, parallel runs of the algorithm are able to generate even better results without violating the real‐time constraint. Results show that the proposed methodology generates competitive results in milliseconds, being able to outperform other heuristics from the literature.     

A Fault-Tolerant and Heuristic Routing Algorithm for Faulty Hypercubes

A fault-tolerant and heuristic routing algorithm for faulty hypercube systems is described.To improve the efficiency,the algorithm adopts a heuristic backtracking strategy and each node has an array to record its all neighbors‘ faulty link information to avoid unnecessary searching for the known faulty links.Furthermore,the faulty link information is dynamically accumulated and the technique of heuristically searching for optimal link is used.The algorithm routes messages through the minimum feasible path between the sender and receiver if at least one such path exists,and takes the optimal path with higher probability when faulty links exist in the faulty hypercube.     

Efficient local search far DAG scheduling

Scheduling DAGs to multiprocessors is one of the key issues in high-performance computing. Most realistic scheduling algorithms are heuristic and heuristic algorithms often have room for improvement. The quality of a scheduling algorithm can be effectively improved by a local search. In this paper, we present a fast local search algorithm based on topological ordering. This is a compaction algorithm that can effectively reduce the schedule length produced by any DAG Scheduling algorithm. Thus, it can improve the quality of existing DAG scheduling algorithms. This algorithm can quickly determine the optimal search direction. Thus, it is of low complexity and extremely fast