Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

Split delivery routing

This article examines a relaxed version of the generic vehicle routing problem. In this version, a delivery to a demand point can be split between any number of vehicles. In spite of this relaxation the problem remains computationally hard. Since only small instances of the vehicle routing problem are known to be solved using exact methods, the vehicle route construction for this problem version is approached using heuristic rules. The main contribution of this article to the existing body of literature on vehicle routing issues in (a) is presenting a new vehicle routing problem amenable to practical applications, and (b) demonstrating the potential for cost savings over similar “traditional” vehicle routing when implementing the model and solutions presented here. The solution scheme allowing for split deliveries is compared with a solution in which no split deliveries are allowed. The comparison is conducted on six sets of 30 problems each for problems of size 75, 115, and 150 demand points (all together 540 problems). For very small demands (up to 10% of vehicle's capacity) no significant difference in solutions is evident for both solution schemes. For the other five problem sets for which point demand exceeds 10% of vehicle's capacity, very significant cost savings are realized when allowing split deliveries. The savings are significant both in the total distance and the number of vehicles required. The vehicles' routes constructed by our procedure tend to cover cohesive geographical zones and retain some properties of optimal solutions.     

一种基于范围表示B树的大容量IPv6路由查表算法

IPv6具有巨大的地址空间,未来要面对的将会是海量IPv6路由表,而且128位的IPv6地址比IPv4需要更多的访存数。算法针对IPv6路由查找问题中的这两个难点,提出利用B树高度较低的优良性质,将前缀转化为范围表保存在B树中,并在结点内部利用分段范围比较树算法来减少访存次数和空间耗费。理论分析和实验表明,该算法能够以很好的性能支持IPv6海量路由表的查找。     

需求可拆分的应急物资调度问题的蚁群算法

应急物资调度问题是个典型的需求可拆分的车辆路径问题,区别于传统的车辆路径问题,将每个需求节点只能由一辆车访问的约束去除,允许需求节点由多辆车进行访问。针对应急物资调度问题的特点,建立相应的多目标车辆路径数学规划模型(SDVRP),并根据模型特点设计改进蚁群优化算法。最后,进行相应的算例分析,验证了该模型和算法的有效性。     

星上路由查找设计与算法实现

针对星上路由器的路由查找功能展开研究。通过分析比较多种路由查找算法,利用软硬件协同设计的思想,给出了星上路由查找的设计与适合硬件查找的Trie树实现。给出了算法实现程序,通过实例分析了算法的优点。结果表明设计可以满足宽带卫星通信系统业务的需求。     

基于多QoS约束的启发式路由选择算法设计与实现

针对时延、路由跳数以及网络资源利率3种约束，结合软件路由器项目，对路由选择算法的网络模型进行了描述和定义，并提出了基于多QoS约束的启发式路由选择算法（H_MCP）。通过在软件路由器上实现和测试，表明该算法具有可行性和启发性。     

Flexibility and complexity in periodic distribution problems

In this paper, we explore trade‐offs between operational flexibility and operational complexity in periodic distribution problems. We consider the gains from operational flexibility in terms of vehicle routing costs and customer service benefits, as well as the costs of operational complexity in terms of modeling, solution methods, and implementation challenges for drivers and customers. The period vehicle routing problem (PVRP) is a variation of the classic vehicle routing problem in which delivery routes are constructed for a period of time; the PVRP with service choice (PVRP‐SC) extends the PVRP to allow service (visit) frequency to become a decision of the model. For the periodic distribution problems represented by PVRP and PVRP‐SC, we introduce operational flexibility levers and a set of quantitative measures to evaluate the trade‐offs between flexibility and complexity. We develop a Tabu Search heuristic to incorporate a range of operational flexibility options. We analyze the potential value and the increased operational complexity of the flexibility levers. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

The fixed charge problem

The fixed charge problem is a nonlinear programming problem of practical interest in business and industry. Yet, until now no computationally feasible exact method of solution for large problems had been developed. In this paper an exact algorithm is presented which is computationally feasible for large problems. The algorithm is based upon a branch and bound approach, with the additional feature that the amount of computer storage required remains constant throughout (for a problem of any given size). Also presented are three suboptimal heuristic algorithms which are of interest because, although they do not guarantee that the true optimal solution will be found, they usually yield very good solutions and are extremely rapid techniques. Computational results are described for several of the heuristic methods and for the branch and bound algorithm.     

Minimizing sums and products of linear fractional functions over a polytope

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999     

Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations

We study a single batching machine scheduling problem with transportation and deterioration considerations arising from steel production. A set of jobs are transported, one at a time, by a vehicle from a holding area to the single batching machine. The machine can process several jobs simultaneously as a batch. The processing time of a job will increase if the duration from the time leaving the holding area to the start of its processing exceeds a given threshold. The time needed to process a batch is the longest of the job processing times in the batch. The problem is to determine the job sequence for transportation and the job batching for processing so as to minimize the makespan and the number of batches. We study four variations (P1, P2, P3, P4) of the problem with different treatments of the two criteria. We prove that all the four variations are strongly NP‐hard and further develop polynomial time algorithms for their special cases. For each of the first three variations, we propose a heuristic algorithm and analyze its worst‐case performance. For P4, which is to find the Pareto frontier, we provide a heuristic algorithm and an exact algorithm based on branch and bound. Computational experiments show that all the heuristic algorithms perform well on randomly generated problem instances, and the exact algorithm for P4 can obtain Pareto optimal schedules for small‐scale instances. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 269–285, 2014     

Transformations of node‐balanced routing problems

This article describes a polynomial transformation for a class of unit‐demand vehicle routing problems, named node‐balanced routing problems (BRP), where the number of nodes on each route is restricted to be in an interval such that the workload across the routes is balanced. The transformation is general in that it can be applied to single or multiple depot, homogeneous or heterogeneous fleet BRPs, and any combination thereof. At the heart of the procedure lies transforming the BRP into a generalized traveling salesman problem (TSP), which can then be transformed into a TSP. The transformed graph exhibits special properties which can be exploited to significantly reduce the number of arcs, and used to construct a formulation for the resulting TSP that amounts to no more than that of a constrained assignment problem. Computational results on a number of instances are presented. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 370–387, 2015     

Worst‐case performance of approximation algorithms for tool management problems

Since the introduction of flexible manufacturing systems, researchers have investigated various planning and scheduling problems faced by the users of such systems. Several of these problems are not encountered in more classical production settings, and so‐called tool management problems appear to be among the more fundamental ones of these problems. Most tool management problems are hard to solve, so that numerous approximate solution techniques have been proposed to tackle them. In this paper, we investigate the quality of such algorithms by means of worst‐case analysis. We consider several polynomial‐time approximation algorithms described in the literature, and we show that all these algorithms exhibit rather poor worst‐case behavior. We also study the complexity of solving tool management problems approximately. In this respect, we investigate the interrelationships among tool management problems, as well as their relationships with other well‐known combinatorial problems such as the maximum clique problem or the set covering problem, and we prove several negative results on the approximability of various tool management problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 445–462, 1999     

基于能量分级和位置预测的高效路由算法

针对车载传感器网络节点移动速度快、网络拓扑结构不稳定、终端传感器节点能量不确定性等特点,提出了一种能量分级和位置预测的高效路由算法ERLP(Energy Rank and Location Prediction based routing)。该算法根据具有不同能量等级的节点将消息传递距离的不同选择那些能量高的节点作为中转节点,并结合节点的分布区域和当前速度,尽量将多个消息副本传递给覆盖不同方向的节点,避免消息传递的局部性。仿真结果表明,与当前典型延迟容忍网络的路由算法相比,ERLP算法在传输成功率、平均延迟时间上具有较大提升。     

直接网络中的自适应路由算法分析

互连网络是大规模并行计算机的重要组成部分，路由算法是其中决定网络性能的重要因素，本文在直接网络结构基础上对路由算法进行讨论，给出了一种分类方法，并着重对采用虫孔路由开关技术的自适应路由算法进行分析，为进一步的评价和设计新的算法提供了参考。     

求解不确定型车辆路径问题的弱鲁棒优化方法

为降低鲁棒优化模型最优解的保守性,以最小化违约车辆数和总惩罚成本为目标,建立针对旅行时间不确定的开放式车辆路径问题的弱鲁棒优化模型。对于不确定数据集的每个取值,该模型的最优解可以使其目标函数值始终不超过某数值,进而改善最优解的保守性。为提高启发式算法发现最优解的概率,提出一种自设计遗传算法对模型进行求解,其主要思想是利用粒子群算法搜索出可使遗传算法预期产生最好解的算法要素,并将其进行组合,从而产生新的遗传算法。采用新产生的遗传算法对模型继续求解,输出最好解。计算结果表明:与以往的鲁棒优化方法相比,弱鲁棒优化方法的最优解的保守性显著降低。     

Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries

We consider the Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSPPD). This problem is characterized by a set of n pickup points and a set of n delivery points. A single product is available at the pickup points which must be brought to the delivery points. A vehicle of limited capacity is available to perform this task. The problem is to determine the tour the vehicle should follow so that the total distance traveled is minimized, each load at a pickup point is picked up, each delivery point receives its shipment and the vehicle capacity is not violated. We present two polynomial‐time approximation algorithms for this problem and analyze their worst‐case bounds. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 654–670, 1999     

蚁群算法在车辆巡回保障中的应用研究

应用蚁群算法（ACA）解决车辆巡回保障问题，建立了车辆巡回保障优化数学模型，对轨迹更新规则进行了重新设定，给出了算法的实现步骤。通过算例分析，将计算结果与遗传算法（GA）和粒子群算法（PSO）作了比较，对模型和算法的正确性、高效性和适用性进行了验证。实验结果表明，该算法可以快速、有效求得车辆巡回保障的优化解，得到车辆巡回保障过程中的较优方案。     

战术MANET中基于多态转移策略的蚁群优化QoS路由算法

战术MANET的QoS路由计算是一个NP完全问题,可以采用蚁群优化算法来求解.为了提高蚁群优化QoS路由算法的效率,降低时延和网络开销,提出了基于多态转移策略的蚁群优化QoS路由算法(MTS-AQRA).MTS-AQRA将链路稳定性和路由拥塞度与常规的QoS路由约束条件结合起来,利用多态转移策略产生的多样化路由搜索蚁群和并行路由搜索处理,能够在MANET网络中快速地建立满足业务QoS要求的稳定路由.仿真实验结果表明,MTS-AQRA在分组到达率、端到端时延、网络吞吐量等指标上综合性能优于AODV、AntHocNet、QoS-Aware ACO等路由算法.     

航空集群机载网络Failure-Oblivious路由策略

航空集群机载网络作为集群成员间信息交互的纽带,其路由策略性能优劣直接影响信息传输实时性与可靠性,从而制约网络化集群作战效能发挥.考虑到航空集群机载网络具有诸多不确定性,为应对路由失效以及尽可能避免路由更新,从路由选择算法的角度,在软件定义网络架构下提出Failure-Oblivious路由策略.与传统路由策略不同的是,...     

Optimal path finding in direction,location, and time dependent environments

This article examines optimal path finding problems where cost function and constraints are direction, location, and time dependent. Recent advancements in sensor and data‐processing technology facilitate the collection of detailed real‐time information about the environment surrounding a ground vehicle, an airplane, or a naval vessel. We present a navigation model that makes use of such information. We relax a number of assumptions from existing literature on path‐finding problems and create an accurate, yet tractable, model suitable for implementation for a large class of problems. We present a dynamic programming model which integrates our earlier results for direction‐dependent, time and space homogeneous environment, and consequently, improves its accuracy, efficiency, and run‐time. The proposed path finding model also addresses limited information about the surrounding environment, control‐feasibility of the considered paths, such as sharpest feasible turns a vehicle can make, and computational demands of a time‐dependent environment. To demonstrate the applicability and performance of our path‐finding algorithm, computational experiments for a short‐range ship routing in dynamic wave‐field problem are presented. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012