We consider a network design application that is modeled as the two-level network design problem under uncertainty. In this problem, one of the two available technologies can be installed on each edge and all customers of the network need to be served by at least the lower level (secondary) technology. The decision maker is confronted with uncertainty regarding the set of primary customers, i.e., the set of nodes that need to be served by the higher level (primary) technology. A set of discrete scenarios associated with the possible realizations of primary customers is available. The network is built in two stages. In the first stage the network topology must be determined. One may decide to install the primary technology on some of the edges in the first stage, or one can wait to see which scenario will be realized, in which case, edges with the installed secondary technology may be upgraded, if necessary to primary technology, but at higher recovery cost. The overall goal then is to build a “recoverable robust” spanning tree in the first stage that serves all customers by at least the lower level technology, and that minimizes the first-stage installation cost plus the worst-case cost needed to upgrade the edges of the selected tree, so that the primary customers of each scenario can be served using the primary technology. We discuss the complexity of the problem, provide mixed-integer programming models, and develop a branch-and-cut algorithm to solve it. Our extensive computational experiments demonstrate the efficacy of our approach.

The multitrip vehicle routing problem (MTVRP) is a variant of the capacitated vehicle routing problem where each vehicle can perform a subset of routes, called a vehicle schedule, subject to maximum driving time constraints. Despite its practical importance, the MTVRP has received little attention in the literature. Few heuristics have been proposed, and only an exact algorithm has been presented for a variant of the MTVRP with customer time window constraints and unlimited driving time for each vehicle. We describe two set-partitioning-like formulations of the MTVRP. The first formulation requires the generation of all feasible routes, whereas the second formulation is based on the generation of all feasible schedules. We study valid lower bounds, based on the linear relaxations of both formulations enforced with valid inequalities, that are embedded into an exact solution method. The computational results show that the proposed exact algorithm can solve MTVRP instances taken from the literature, with up to 120 customers.

In this paper we study a railway optimization problem known as the Train Unit Assignment Problem. A train unit consists of a self-contained train with an engine and a set of wagons with passenger seats. Given a set of timetabled train trips, each with a required number of passenger seats, and a set of train units, each with a given number of available seats, the problem calls for the best assignment of the train units to the trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. We propose a heuristic algorithm based on the computation of a lower bound obtained by solving an Integer Linear Programming model that gives the optimal solution in a "peak period" of the day. The performance of the heuristic algorithm is computationally evaluated on real-world instances provided by a regional Italian Train Operator. The results are compared with those of existing methods from the literature, showing that the new method is able to obtain solutions of good quality in much shorter computing times.

Given a graph G = (N, E), the covering salesman problem (CSP) is to identify the minimum length tour “covering” all the nodes. More specifically, it seeks the minimum-length tour visiting a subset of the nodes in N such that each node i not on the tour is within a predetermined distance di of a node on the tour. In this paper, we define and develop a generalized version of the CSP, and we refer to it as the generalized covering salesman problem (GCSP). Here, each node i needs to be covered at least ki times, and there is a cost associated with visiting each node. We seek a minimum-cost tour such that each node i is covered at least ki times by the tour. We define three variants of the GCSP. In the first case, each node can be visited by the tour at most once. In the second case, visiting a node i more than once is possible, but an overnight stay is not allowed (i.e., to revisit a node i, the tour has to visit another node before it can return to i). Finally, in the third case, the tour can visit each node more than once consecutively. In this paper, we develop two local search heuristics to find high-quality solutions to the three GCSP variants. To test the proposed algorithms, we generated data sets based on traveling salesman problem library instances. Because the CSP and the generalized traveling salesman problem are special cases of the GCSP, we tested our heuristics on both of those problems as well. Overall, the results show that our proposed heuristics find high-quality solutions very rapidly.

Abstract We study the equality generalized traveling salesman problem (E‐GTSP), which is a variant of the well‐known traveling salesman problem. We are given an undirected graph G = (V,E), with set of vertices V and set of edges E, each with an associated cost. The set of vertices is partitioned into clusters. E‐GTSP is to find an elementary cycle visiting exactly one vertex for each cluster and minimizing the sum of the costs of the traveled edges. We propose a multistart heuristic, which iteratively starts with a randomly chosen set of vertices and applies a decomposition approach combined with improvement procedures. The decomposition approach considers a first phase to determine the visiting order of the clusters and a second phase to find the corresponding minimum cost cycle. We show the effectiveness of the proposed approach on benchmark instances from the literature. On small instances, the heuristic always identifies the optimal solution rapidly and outperforms all known heuristics; on larger instances, the heuristic always improves, in comparable computing times, the best known solution values obtained by the genetic algorithm recently proposed by Silberholz and Golden. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Train Routing is a problem that arises in the early phase of the passenger railway planning process, usually several months before operating the trains. The main goal is to assign each train a stopping platform and the corresponding arrival/departure paths through a railway station. It is also called Train Platforming when referring to the platform assignment task. Railway stations often represent bottlenecks and train delays can easily disrupt the routing schedule. Thereby railway stations are responsible for a large part of the delay propagation in the whole network. In this research we present different models to compute robust routing schedules and we study their power in an online context together with different re-scheduling strategies. We also design a simulation framework and use it to evaluate and compare the effectiveness of the proposed robust models and re-scheduling algorithms using real-world data from Rete Ferroviaria Italiana, the main Italian Railway Infrastructure Manager.

We consider a particular bin packing problem in which some pairs of items may be in conflict and cannot be assigned to the same bin. The problem, denoted as the bin packing problem with conflicts, is of practical and theoretical interest because of its many real-world applications and because it generalizes both the bin packing problem and the vertex coloring problem. We present new lower bounds, upper bounds, and an exact approach, based on a set covering formulation solved through a branch-and-price algorithm. We investigate the behavior of the proposed procedures by means of extensive computational results on benchmark instances from the literature.

Given an undirected graph G = (V, E), the vertex coloring problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. In this paper, we propose a metaheuristic approach for VCP that performs two phases: the first phase is based on an evolutionary algorithm, whereas the second one is a postoptimization phase based on the set covering formulation of the problem. Computational results on a set of DIMACS instances show that the overall algorithm is able to produce high-quality solutions in a reasonable amount of time. For four instances, the proposed algorithm is able to improve the best-known solution while for almost all the remaining instances, it finds the best-known solution in the literature.

Several combinatorial optimization problems can be formulated as large set-covering problems. In this work, we use the set-covering formulation to obtain a general heuristic algorithm for this type of problem, and describe our implementation of the algorithm for solving two variants of the well-known (one-dimensional) bin-packing problem: the two-constraint bin-packing problem and the basic version of the two-dimensional bin-packing problem, where the objects cannot be rotated and no additional requirements are imposed. In our approach, both the “column-generation” and the “column-optimization” phases are heuristically performed. In particular, in the first phase, we do not generate the entire set of columns, but only a small subset of it, by using greedy procedures and fast constructive heuristic algorithms from the literature. In the second phase, we solve the associated set-covering instance by means of a Lagrangian-based heuristic algorithm. Extensive computational results on test instances from the literature show that, for the two considered problems, this approach is competitive, with respect to both the quality of the solution and the computing time, with the best heuristic and metaheuristic algorithms proposed so far.

We describe a new variant, called granular tabu search, of the well-known tabu-search approach. The method uses an effective intensification/diversification tool that can be successfully applied to a wide class of graph-theoretic and combinatorial-optimization problems. Granular tabu search is based on the use of drastically restricted neighborhoods, not containing the moves that involve only elements that are not likely to belong to good feasible solutions. These restricted neighborhoods are called granular, and may be seen as an efficient implementation of candidate-list strategies proposed for tabu-search algorithms. Results of computational testing of the proposed approach on the well-known symmetric capacitated and distance-constrained vehicle-routing problem are discussed, showing that the approach is able to determine very good solutions within short computing times.

The Quadratic Knapsack Problem (QKP) calls for maximizing a quadratic objective function subject to a knapsack constraint, where all coefficients are assumed to be nonnegative and all variables are binary. The problem has applications in location and hydrology, and generalizes the problem of checking whether a graph contains a clique of a given size. We propose an exact branch-and-bound algorithm for QKP, where upper bounds are computed by considering a Lagrangian relaxation that is solvable through a number of (continuous) knapsack problems. Suboptimal Lagrangian multipliers are derived by using subgradient optimization and provide a convenient reformulation of the problem. We also discuss the relationship between our relaxation and other relaxations presented in the literature. Heuristics, reductions, and branching schemes are finally described. In particular, the processing of each node of the branching tree is quite fast: We do not update the Lagrangian multipliers, and use suitable data structures to compute an upper bound in linear expected time in the number of variables. We report exact solution of instances with up to 400 binary variables, i.e., significantly larger than those solvable by the previous approaches. The key point of this improvement is that the upper bounds we obtain are typically within 1% of the optimum, but can still be derived effectively. We also show that our algorithm is capable of solving reasonable-size Max Clique instances from the literature.

In the Orienteering Problem (OP), we are given an undirected graph with edge weights and node prizes. The problem calls for a simple cycle whose total edge weight does not exceed a given threshold, while visiting a subset of nodes with maximum total prize. This NP-hard problem arises in routing and scheduling applications. We describe a branch-and-cut algorithm for finding an optimal OP solution. The algorithm is based on several families of valid inequalities. We also introduce a family of cuts, called conditional cuts, which can cut off the optimal OP solution, and propose an effective way to use them within the overall branch-and-cut framework. Exact and heuristic separation algorithms are described, as well as heuristic procedures to produce near-optimal OP solutions. An extensive computational analysis on several classes of both real-world and random instances is reported. The algorithm proved to be able to solve to optimality large-scale instances involving up to 500 nodes, within acceptable computing time. This compares favorably with previous published methods.

In this paper, we investigate the possibility of integrating Artificial Intelligence (AI) and Operations Research (OR) techniques for solving the Crew Rostering Problem (CRP). CRP calls for the optimal sequencing of a given set of duties into rosters satisfying a set of constraints. The optimality criterion requires the minimization of the number of crews needed to cover the duties. This kind of problem has been traditionally solved by OR techniques. In recent years, a new programming paradigm based on Logic Programming, named Constraint Logic Programming (CLP), has been successfully used for solving hard combinatorial optimization problems. CLP maintains all the advantages of logic programming such as declarativeness, non-determinism and an incremental style of programming, while overcoming its limitations, mainly due to the inefficiency in exploring the search space. CLP achieves good results on hard combinatorial optimization problems which, however, are not comparable with those achieved by OR approaches. Therefore, we integrate both techniques in order to design an effective heuristic algorithm for CRP which fully exploits the advantages of the two methodologies: on the one hand, we maintain the declarativeness of CLP, its ease of representing knowledge and its rapid prototyping; on the other hand, we inherit from OR some efficient procedures based on a mathematical approach to the problem. Finally, we compare the results we achieved by means of the integration with those obtained by a pure OR approach, showing that AI and OR techniques for hard combinatorial optimization problems can be effectively integrated. © 1998 John Wiley & Sons, Ltd.

Abstract The symmetric Generalized Traveling Salesman Problem (GTSP) is a variant of the classical symmetric Traveling Salesman Problem, in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. A different version of the problem, called E‐GTSP, arises when exactly one node for each cluster has to be visited. Both GTSP and E‐GTSP are NP‐hard problems and find practical applications in routing, scheduling, and location‐routing. in this paper, we model GTSP and E‐GTSP as integer linear programs and study the facial structure of the corresponding polytopes. in a companion paper, Theresults described in this work have been used to design a branch‐and‐cut algorithm for the exact solution of instances up to 442 nodes.

A lowest-first, branch-and-bound algorithm for the Asymmetric Traveling Salesman Problem is presented. The method is based on the Assignment Problem relaxation and on a subtour elimination branching scheme . The effectiveness of the algorithm derives from reduction procedures and parametric solution of the relaxed problems associated with the nodes of the branch-decision tree. Large-size, uniformly, randomly generated instances of complete digraphs with up to 2000 vertices are solved on a DECstation 5000/240 computer in less than 3 minutes of CPU time. In addition, we solved on a PC 486/33 no wait flow shop problems with up to 1000 jobs in less than 11 minutes and real-world stacker crane problems with up to 443 movements in less than 6 seconds.

The Fortran code CDT, implementing an algorithm for the asymmetric traveling salesman problem , is presented. The method is based on the Assignment Problem relaxation and on a subtour elimination branching scheme . The effectiveness of the implementation derives from reduction procedures and parametric solution of the relaxed problems associated with the nodes of the branch-decision tree.

An efficient algorithm for the solution of the Min-Sum Arborescence Problem with fixed root-vertex in complete digraphs is presented. The algorithm is based on the well-known Edmonds method. The new approach makes use of simple data structures leading to improvements affecting both computing times and memory requirements. Further improvements are obtained by using a new algorithm based on the solution of a sparse problem. The linear programming reduced costs associated with the arcs are also computed. A FORTRAN implementation is described; the corresponding code is available, on request, from the authors. Extensive computational results on both real-world and random instances are given, showing the effectiveness of the proposed algorithms. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A parallel version of the shortest augmenting path algorithm for the assignment problem 1s described.Although generating the initial dual solution and partial assignment in parallel does not require substantive changes in the sequential algorlthm, using several augmenting paths in parallel does require a new dual variable recalculation Graph Theory -graph algorithms; network problems: path and cmcmt problems: I. 1.

Abstract The Vehicle Scheduling Problem concerns the assigning of a set of time‐tabled trips to vehicles so as to minimize a given cost function. We consider the NP‐hard Multiple Depot case in which, in addition, one has to assign vehicles to depots. Different lower bounds based on assigment relaxation and on connectivity constraints are presented and combined in an effective bounding procedure. A strong dominance procedure derived from new dominance criteria also described. A branch and bound algorithm is finally proposed. Computational results are given.

article Free AccessArtifacts AvailableArtifacts Evaluated & ReusableAlgorithm 632: A program for the 0–1 multiple knapsack problem Authors: Silvano Martello DEIS, University of Bologna, Viale Risorgimento 2, Bologne, Italy DEIS, University of Bologna, Viale Risorgimento 2, Bologne, ItalyView Profile , Paolo Toth University of Florence University of FlorenceView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 11Issue 2pp 135–140https://doi.org/10.1145/214392.214397Published:01 June 1985Publication History 15citation1,386DownloadsMetricsTotal Citations15Total Downloads1,386Last 12 Months38Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract The problem considered is that of removing the maximum number of edges from a digraph without affecting its reachability properties. The worst‐case performance of algorithms from the related literature is analyzed; it is found that Hsu's method contains some mistakes. A new algorithm is presented, based on a reduction procedure and on a branch and bound search; its efficiency is studied both theoretically and through computational experiments.

Abstract It is well‐known that few combinatorial optimization problems can be solved effectively by dynamic programming alone, since the number of vertices of the state space graph is enormous. What we are proposing here is a general relaxation procedure whereby the state‐space associated with a given dynamic programming recursion is relaxed in such a way that the solution to the relaxed recursion provides a bound which could be embedded in general branch and bound schemes for the solution of the problem. This state space relaxation method is analogous to Langrangian relaxation in integer programming. This paper gives a survey of this new methodology, and gives, as examples, applications to the traveling salesman problem (TSP), the time‐constrained TSP and the vehicle routing problem (VRP). Valid state space relaxations are discussed for these problems and several bounds are derived in each case. Subgradient optimization and “state space ascent” are discussed as methods of maximizing the resulting lower bounds. More details of the procedures surveyed in this paper can be found in [2, 3, 4].

article Free AccessArtifacts AvailableArtifacts Evaluated & ReusableAlgorithm 548: Solution of the Assignment Problem [H] Authors: Giorgio Carpaneto Istituto di Automatica, Facoltà di Ingegneria, Universita Di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy Istituto di Automatica, Facoltà di Ingegneria, Universita Di Bologna, Viale Risorgimento 2, 40136 Bologna, ItalyView Profile , Paolo Toth Istituto di Automatica, Facoltà di Ingegneria, Universita Di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy Istituto di Automatica, Facoltà di Ingegneria, Universita Di Bologna, Viale Risorgimento 2, 40136 Bologna, ItalyView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 6Issue 1pp 104–111https://doi.org/10.1145/355873.355883Published:01 March 1980Publication History 80citation1,525DownloadsMetricsTotal Citations80Total Downloads1,525Last 12 Months60Last 6 weeks13 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF