Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints

In this paper, we extend the multiple traveling repairman problem by considering a limitation on the total distance that a vehicle can travel; the resulting problem is called the multiple traveling repairmen problem with distance constraints (MTRPD). In the MTRPD, a fleet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from and ends at the depot is not allowed to travel a distance longer than a predetermined limit and each customer must be visited exactly once. The objective is to minimize the total waiting time of all customers after the vehicles leave the depot. To optimally solve the MTRPD, we propose a new exact branch-and-price-and-cut algorithm, where the column generation pricing subproblem is a resource-constrained elementary shortest-path problem with cumulative costs. An ad hoc label-setting algorithm armed with bidirectional search strategy is developed to solve the pricing subproblem. Computational results show the effectiveness of the proposed method. The optimal solutions to 179 out of 180 test instances are reported in this paper. Our computational results serve as benchmarks for future researchers on the problem.     

Two improved formulations for the minimum latency problem

In network problems, latency is associated with the metric used to evaluate the length of the path from a root vertex to each vertex in the network. In this work we are dealing with two applications or variations of the minimum latency problem known as the repairman problem and the deliveryman problem. We have developed two integer formulations for the minimum latency problem and compared them with other two formulations from the literature for the time-dependent traveling salesman problem. The present work highlights the similarities and differences between the different formulations. In addition, we discuss the convenience of including a set of constraints in order to reduce the computation time needed to reach the optimal solution. We have carried out extensive computational experimentation on asymmetrical instances, since they provide the characteristics of the deliveryman and repairman problems in a better way.     

Expanding neighborhood search–GRASP for the probabilistic traveling salesman problem

The Probabilistic Traveling Salesman Problem is a variation of the classic traveling salesman problem and one of the most significant stochastic routing problems. In probabilistic traveling salesman problem only a subset of potential customers need to be visited on any given instance of the problem. The number of customers to be visited each time is a random variable. In this paper, a variant of the well-known Greedy Randomized Adaptive Search Procedure (GRASP), the Expanding Neighborhood Search–GRASP, is proposed for the solution of the probabilistic traveling salesman problem. expanding neighborhood search–GRASP has been proved to be a very efficient algorithm for the solution of the traveling salesman problem. The proposed algorithm is tested on a numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP algorithm and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number of implementations of the Ant Colony Optimization algorithm from the literature and in six out of ten cases the proposed algorithm gives a new best solution.     

GRASP with path relinking for the orienteering problem

In this paper, we address an optimization problem resulting from the combination of the well-known travelling salesman and knapsack problems. In particular, we target the orienteering problem, originated in the context of sport, which consists of maximizing the total score associated with the vertices visited in a path within the available time. The problem, also known as the selective travelling salesman problem, is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in routing and tourism. We propose a heuristic method—based on the Greedy Randomized Adaptive Search Procedure (GRASP) and the Path Relinking methodologies—for finding approximate solutions to this optimization problem. We explore different constructive methods and combine two neighbourhoods in the local search of GRASP. Our experimentation with 196 previously reported instances shows that the proposed procedure obtains high-quality solutions employing short computing times.     

The delivery man problem on a tree network

This note considers a variant of the traveling salesman problem in which we seek a route that minimizes the total of the vertex arrival times. This problem is called the deliverly man problem. The traveling salesman problem is NP-complete on a general network and trivial on a tree network. The delivery man problem is also NP-complete on a general network but far from trivial on a tree network. Various characteristics of the delivery man problem for tree networks are explored and a pseudo-polynomial time solution algorithm is proposed.This research was sponsored by NSF Grant #ECS-8104647.     

The Efficiency of Two Groups of <Emphasis Type="Italic">N</Emphasis> Machines Served by a Single Robot

Many modern manufacturing facilities use carousel conveyors for storage of work-in-progress, and automatic devices to place and retrieve items in and from the storage locations. The ‘carousel conveyor problem’ is directly related to the ‘patrolling repairman problem’ reported by others. In this paper, we extend the model to include a single robot serving two or more carousels. The approach makes use of known results for the patrolling repairman.     

Applying GRASP to solve the multi-item three-echelon uncapacitated facility location problem

This paper considers a production–distribution problem that consists of defining the flow of produced products from manufacturing plants to clients (markets) via a set of warehouses. The problem also consists of defining the location of such warehouses that have unlimited storage capacity. This problem is known in the literature as the three-echelon uncapacitated facility location problem (TUFLP), and is known to be NP-hard when the objective function is to minimize the total cost of warehouse location and production and distribution of products. This paper proposes a Greedy Randomized Adaptive Search Procedure (GRASP) to solve the multi-item version of the TUFLP. Computational experiments are conducted using known instances from the literature. Solutions obtained using GRASP are compared against both optimal solutions and lower bounds obtained using mathematical programming. Results show that proposed algorithm performs well, obtaining good solutions (and even the optimal values) in less computational time than the mixed-integer linear programming model.     

A nonmonotone GRASP

A greedy randomized adaptive search procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result. The GRASP local search applies iterative improvement until a locally optimal solution is found. During this phase, starting from the current solution an improving neighbor solution is accepted and considered as the new current solution. In this paper, we propose a variant of the GRASP framework that uses a new “nonmonotone” strategy to explore the neighborhood of the current solution. We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on three classical hard combinatorial optimization problems: the maximum cut problem (MAX-CUT), the weighted maximum satisfiability problem (MAX-SAT), and the quadratic assignment problem (QAP).     

A GRASP metaheuristic for humanitarian aid distribution

Large scale disasters, natural or human-made, have huge consequences on people and infrastructures. After a disaster strikes, the distribution of humanitarian aid to the population affected is one of the main operations to be carried out, and several crucial decisions must be made in a short time. This paper addresses a last-mile distribution problem in disaster relief operations, under insecure and uncertain conditions. A model is presented that takes into account the cost and time of operation, the security and reliability of the routes, and the equity of aid handed out. The output of the model consists of a detailed set of itineraries that can be used to build an implementable distribution plan. Given its high complexity, the resulting problem is solved using a multi-criteria metaheuristic approach. In particular, a constructive algorithm and a GRASP based metaheuristic are developed, which are tested in a case study based on the 2010 Haiti earthquake.     

A GRASP + ILP-based metaheuristic for the capacitated location-routing problem

In this paper we present a three-phase heuristic for the Capacitated Location-Routing Problem. In the first stage, we apply a GRASP followed by local search procedures to construct a bundle of solutions. In the second stage, an integer-linear program (ILP) is solved taking as input the different routes belonging to the solutions of the bundle, with the objective of constructing a new solution as a combination of these routes. In the third and final stage, the same ILP is iteratively solved by column generation to improve the solutions found during the first two stages. The last two stages are based on a new model, the location-reallocation model, which generalizes the capacitated facility location problem and the reallocation model by simultaneously locating facilities and reallocating customers to routes assigned to these facilities. Extensive computational experiments show that our method is competitive with the other heuristics found in the literature, yielding the tightest average gaps on several sets of instances and being able to improve the best known feasible solutions for some of them.     

Optimal repair allocation in a series system expected discounted operation time criterion

Consider a series system with n repairable components maintained by a single repairman. The following assumptions are made. Component failure and repair times are independent, exponentially distributed, random variables. Component failures can occur even while the system is not functioning and it is possible to reassign the repairman among failed components instantaneously. It is shown that the policy which always assigns the repairman to the failed component with the smallest failure rate among the failed ones maximizes the expected discounted system operation time irrespective of the values of the repair rates and the discount rate     

有优先权且工作故障与贮备故障后的修理时间不相同的温贮备系统的可靠性分析

为了解决开关寿命为连续随机变量且部件工作故障的修理时间与贮备故障后的修理时间各不相同的问题,利用Markov过程理论和Laplace变换方法,研究了有优先权的两不同型部件和两不同修理工组成的温贮备可修系统.假定部件的工作寿命、贮备寿命、工作故障的修理时间和贮备故障的修理时间均服从不同的指数分布,得到了该系统的可靠度Laplace变换和系统的首次故障前平均时间的解析表达式.     

一种新型的N部件串联可修系统及其可靠性分析

本文研究一种Ⅳ部件串联可修系统的一个新模型，该模型在经典。部件串联可修系统中引入了修理工可多重延误休假的概念，并且考虑了修理工使用修理设备在修理失效部件过程中可能因修理设备失效而立即更换修理设备对整个系统可靠性造成的影响,假定修理工的延误休假时间、部件的寿命和修理设备的寿命均服从指数分布，部件的修理时间、修理设备的更换时间和修理工的休假时间均服从一般连续型分布，通过使用补充变量法和广义马尔可夫过程方法得到了系统和修理设备的一些重要可靠性指标．     

单部件可修系统的一个几何过程维修模型

本文研究了单部件、一个修理工组成的可修系统的最优更换问题,假定系统不能修复如新,以系统年龄T为策略,利用几何过程求出了最优的策略T^*,使得系统经长期运行单位时间内期望效益达到最大,并求出了系统经长期运行单位时间内期望效益的显式表达式。在一定条件下证明了T^*的唯一存在性。最后还证明了策略T^*比文献[6]中的策略T^*优。     

A deteriorating system with its repairman having multiple vacations

This paper considers a repairable system with a repairman, who can take multiple vacations. If the system fails and the repairman is on vacation, it will wait for repair until the repairman is available. Assume that the system cannot be repaired “as good as new” after failures. Under these assumptions, using the geometric process and the supplementary variable technique, some important reliability indexes are derived, such as the system reliability, availability, rate of occurrence of failures, etc. According to the renewal reward theorem, the explicit expression of the expected profit per unit time is obtained. Finally, a numerical example is given to illustrate that there exists an optimal replacement policy N∗, which maximizes the value of the expected profit rate after a long time run.     

Bilevel control of degraded machining system with warm standbys, setup and vacation

In this paper, we study (N, L) switch-over policy for machine repair model with warm standbys and two repairmen. The repairman (R₁) turns on for repair only when N-failed units are accumulated and starts repair after a set up time which is assumed to be exponentially distributed. As soon as the system becomes empty, the repairman (R₁) leaves for a vacation and returns back when he finds the number of failed units in the system greater than or equal to a threshold value N. Second repairman (R₂) turns on when there are L(>N) failed units in the system and goes for a vacation if there are less than L failed units. The life time and repair time of failed units are assumed to be exponentially distributed. The steady state queue size distribution is obtained by using recursive method. Expressions for the average number of failed units in the queue and the average waiting time are established.     

专职修理工多重休假且修理设备可更换的k/n(G)表决系统研究

讨论专职修理工多重休假,修理设备可发生失效且可更换的k/n（G）表决可修系统.当系统中没有故障部件时,专职修理工开始一次休假,在此期间,若有工作部件发生故障,则立即指派普通修理工修理故障部件,一直持续到系统中无故障部件或专职修理工休假回来.利用马尔可夫过程理论和矩阵解法,给出了系统瞬态和稳态下的可用度和故障频度、可靠度、系统首次故障前的平均时间、修理设备处于更换状态的概率等指标的表达式.在此基础上,基于不同的初始条件研究了相关指标随时间的变化情况.最后,特殊情形的讨论验证了所得结果的正确性.     

Traveling salesman games

In this paper we discuss the problem of how to divide the total cost of a round trip along several institutes among the institutes visited. We introduce two types of cooperative games—fixed-route traveling salesman games and traveling salesman games—as a tool to attack this problem. Under very mild conditions we prove that fixed-route traveling salesman games have non-empty cores if the fixed route is a solution of the classical traveling salesman problem. Core elements provide us with fair cost allocations. A traveling salesman game may have an empty core, even if the cost matrix satisfies the triangle inequality. In this paper we introduce a class of matrices defining TS-games with non-empty cores.     

一个可修系统的最优更换模型

本文考虑了单部件、一个修理工组成的可修系统，在故障系统不能“修复如新”的前提下，我们利用几何过程，以系统年龄Ｔ为策略，选择最优的Ｔ使得系统经长期运行单位时间的期望效益达到最大．本文还在一定的条件下证明了最优更换策略Ｔ的唯一存在，且求出了系统经长期运行单位时间的最大期望效益的明显表达式．     

具有单重休假和修复不如新的两部件并联系统

为了解决由"修复非新"部件组成的具有休假的可修型系统,运用几何过程理论、补充变量法和拉普拉斯变换工具,研究了由两个不同型部件和一个修理工组成的可修型并联系统.假设两个部件的工作寿命和修理时间均服从不同的指数分布,修理工可休假,对部件1的修理是几何修理而对部件2的修理则是修复如新,得到了系统的可用度、可靠度和系统首次故障前平均时间等可靠性指标.成果具有一定的理论和实际意义.