ABSTRACT Nearest, Farthest, and Cheapest Insertion are three well‐known polynomial‐time approximation algorithms for the Traveling Salesman Problem (TSP). This paper aims to report on a fourth insertion algorithm, called Largest Insertion, from both a theoretical and an experimental viewpoint. On the theoretical side, the worst‐case performance of the algorithm is studied: In particular, it is shown that there exist instances for which the value of the solution computed by Largest Insertion approaches three times the optimum in the Euclidean plane. On the experimental side, the outcome of computational tests is reported: When compared with the other three insertion algorithms, Largest Insertion scores second on random Euclidean instances and first on large random graphical instances.

We consider a combinatorial optimization problem for spatial information cloaking. The problem requires computing one or several disjoint arborescences on a graph from a predetermined root or subset of candidate roots, so that the number of vertices in the arborescences is minimized but a given threshold on the overall weight associated with the vertices in each arborescence is reached. For a single arborescence case, we solve the problem to optimality by designing a branch-and-cut exact algorithm. Then we adapt this algorithm for the purpose of pricing out columns in an exact branch-and-price algorithm for the multiarborescence version. We also propose a branch-and-price-based heuristic algorithm, where branching and pricing, respectively, act as diversification and intensification mechanisms. The heuristic consistently finds optimal or near optimal solutions within a computing time, which can be three to four orders of magnitude smaller than that required for exact optimization. From an application point of view, our computational results are useful to calibrate the values of relevant parameters, determining the obfuscation level that is achieved. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0813 .

We study a prize-collecting single-machine scheduling problem with hard deadlines, where the objective is to minimize the difference between the total tardiness and the total prize of the selected jobs. This problem is motivated by industrial applications, both as a stand-alone model and as a pricing subproblem in column-generation algorithms for parallel machine scheduling problems. A preprocessing rule is devised to identify jobs that cannot belong to any optimal schedule. The resulting reduced problem is solved to optimality by a branch-and-bound algorithm and two integer linear programming formulations. The algorithm and the formulations are experimentally compared on randomly generated benchmark instances.

In this article, we consider a variation of the vehicle routing problem arising in the optimization of waste management systems. Constraints imposing adequate level of service to the citizens and even workload among the drivers make the problem challenging and ask for the design of specialized algorithmic approaches. We propose an exact optimization algorithm, in which dynamic generation of rows and columns is done in a branch‐and‐bound framework; exact and heuristic algorithms are proposed for the pricing problem. Experimental tests on data‐sets from the literature show that our algorithm outperforms previous ones and it is able to solve instances of realistic size to proven optimality in reasonable computing time. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(4), 282–291 2014

This paper describes the algorithms used in a planning and scheduling software tool developed for the European Space Agency in the framework of the Mars Express mission. The planning and scheduling algorithm computes a feasible schedule for the transmission of telecommands (TCs) from the ground segment to the space segment, complying with a number of technical constraints. Owing to the distance between Mars and Earth, it is important that the robustness of the schedule is taken into account because repair operations may be very time consuming or even impossible. For this reason, besides the maximization of the number of TCs transmitted from Earth to Mars, the scheduler is also designed to maximize the number of full confirmations and secondary time windows, which are two special characteristics of the Mars Express schedule explicitly designed for the sake of robustness. Besides the maximization of robustness, the scheduling algorithm that can run with different settings can be used to optimize some secondary figures of merit, such as the average saturation of the memory devices of the space segment and the usage of the time windows available for communication. Computational results on real instances are presented.

The problem of computing a schedule of maximum robustness for the Mars Express mission is formulated and solved via linear programming (LP). We also provide a characterization of "easy" and "difficult" instances such that the former ones can be solved to optimality directly, without having recourse to any optimization algorithm. In both cases, provably optimal solutions are obtained in shorter computing time compared to previously published approaches. Starting from the simplified model already described in the literature, we extend it to consider real constraints. For this purpose, we define an integer LP model with four different objective functions and develop a decision support system based on hierarchical optimization of the first two objectives and multicriteria optimization of the other two.

Abstract The resource constrained elementary shortest path problem (RCESPP) arises as a pricing subproblem in branch‐and‐price algorithms for vehicle‐routing problems with additional constraints. We address the optimization of the RCESPP and we present and compare three methods. The first method is a well‐known exact dynamic‐programming algorithm improved by new ideas, such as bidirectional search with resource‐based bounding. The second method consists in a branch‐and‐bound algorithm, where lower bounds are computed by dynamic‐programming with state‐space relaxation; we show how bounded bidirectional search can be adapted to state‐space relaxation and we present different branching strategies and their hybridization. The third method, called decremental state‐space relaxation, is a new one; exact dynamic‐programming and state‐space relaxation are two special cases of this new method. The experimental comparison of the three methods is definitely favorable to decrement state‐space relaxation. Computational results are given for different kinds of resources, arising from the capacitated vehicle‐routing problem, the vehicle‐routing problem with distribution and collection, and the vehicle‐routing problem with capacities and time windows. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract The capacitated p‐median problem is the variation of the well‐known p‐median problem in which a demand is associated to each user, a capacity is associated to each candidate median, and the total demand of the users associated to the same median must not exceed its capacity. We present a branch‐and‐price algorithm, that exploits column generation, heuristics and branch‐and‐bound to compute optimal solutions. We compare our branch‐and‐price algorithm with other methods proposed so far, and we present computational results both on test instances taken from the literature and on random instances with different values of the ratio between the number of medians and the number of users. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 125–142 2005