A simulated annealing approach to the traveling tournament problem

Automating the scheduling of sport leagues has received considerable attention in recent years, as these applications involve significant revenues and generate challenging combinatorial optimization problems. This paper considers the traveling tournament problem (TTP) which abstracts the salient features of major league baseball (MLB) in the United States. It proposes a simulated annealing algorithm (TTSA) for the TTP that explores both feasible and infeasible schedules, uses a large neighborhood with complex moves, and includes advanced techniques such as strategic oscillation and reheats to balance the exploration of the feasible and infeasible regions and to escape local minima at very low temperatures. TTSA matches the best-known solutions on the small instances of the TTP and produces significant improvements over previous approaches on the larger instances. Moreover, TTSA is shown to be robust, because its worst solution quality over 50 runs is always smaller or equal to the best-known solutions. A Preliminary version of this paper was presented at the CP'AI'OR'03 Workshop.     

The traveling purchaser problem with budget constraint

Let us consider a set of markets plus a depot and a set of products for each of which a positive demand is specified. Each product is made available in a subset of markets in each of which only a given quantity, less than or equal to the required one, can be purchased at a given unit price. The distance between each couple of markets and between each market and the depot is known. The Traveling Purchaser Problem with Budget constraint (TPP-B) looks for a simple cycle starting at and ending to the depot and visiting a subset of markets at a minimum traveling cost and such that the demand for each product is satisfied and the cost globally spent for purchasing the products does not exceed a defined budget threshold. As the TPP also this problem arises in several application domains, but while the former has been largely studied, very few contributions exist in the literature for the TPP-B. We propose and compare two solution algorithms, an enhanced local-search heuristic and a variable neighborhood search (VNS) approach also tested in a multi-start variant. The proposed algorithms have been used to solve both the capacitated and the uncapacitated version of the problem. Test problems have been obtained by adding a budget constraint to known benchmark instances for the TPP.     

The generalized covering traveling salesman problem

In this paper we develop a problem with potential applications in humanitarian relief transportation and telecommunication networks. Given a set of vertices including the depot, facility and customer vertices, the goal is to construct a minimum length cycle over a subset of facilities while covering a given number of customers. Essentially, a customer is covered when it is located within a pre-specified distance of a visited facility on the tour. We propose two node-based and flow-based mathematical models and two metaheuristic algorithms including memetic algorithm and a variable neighborhood search for the problem. Computational tests on a set of randomly generated instances and on set of benchmark data indicate the effectiveness of the proposed algorithms.     

The pickup and delivery traveling salesman problem with first-in-first-out loading

This paper addresses a variation of the traveling salesman problem with pickup and delivery in which loading and unloading operations have to be executed in a first-in-first-out fashion. It provides an integer programming formulation of the problem. It also describes five operators for improving a feasible solution, and two heuristics that utilize these operators: a probabilistic tabu search algorithm, and an iterated local search algorithm. The heuristics are evaluated on data adapted from TSPLIB instances.     

The Steiner traveling salesman problem with online advanced edge blockages

The package delivery in an urban road network is formulated as an online Steiner traveling salesman problem, where the driver (i.e. the salesman) receives road (i.e. edge) blockage messages when he is at a certain distance to the respective blocked edges. Such road blockages are referred to as advanced information. With these online advanced road blockages, the driver wishes to deliver all the packages to their respective customers and returns back to the service depot through a shortest route. During the entire delivery process, there will be at most k road blockages, and they are non-recoverable. When the driver knows about road blockages at a distance $\alpha \mathrm{OPT}$, where $\alpha \in [0,1]$ is referred to as the forecasting ratio and OPT denotes the length of the offline shortest route, we first prove that $\max \left\{\right(1-2\alpha )k+1,1\}$ is a lower bound on the competitive ratio. We then present a polynomial time online algorithm with a competitive ratio very close to this lower bound. Computational results show that our algorithm is efficient and produces near optimal solutions. Similar results for a variation, in which the driver does not need to return to the service depot, are also achieved.     

Heuristics for the traveling repairman problem with profits

In the traveling repairman problem with profits, a repairman (also known as the server) visits a subset of nodes in order to collect time-dependent profits. The objective consists of maximizing the total collected revenue. We restrict our study to the case of a single server with nodes located in the Euclidean plane. We investigate the properties of this problem, and we derive a mathematical model assuming that the number of nodes to be visited is known in advance. We describe a tabu search algorithm with multiple neighborhoods, we test its performance by running it on instances from the literature and compare the outcomes with an upper bound. We conclude that the tabu search algorithm finds good-quality solutions fast, even for large instances.     

改进的MIMIC算法求解旅行商问题

为了有效解决组合优化领域的旅行商问题,提出了一种改进的双变量相关的分布估计算法-MIMIC 算法.改进的MIMIC 算法将原有的二进制编码表达方式改为十进制编码,建立了求解旅行商问题的概率模型,描述了搜索空间上旅行路径的分布,以旅行路径的概率分布模型为基础进行随机采样,指导后代种群的产生,实现种群的进化以达到搜索最优旅行路径的目的.仿真实验表明,提出的改进的 MIMIC 算法是一种求解 TSP 问题的有效方法.     

Models for a traveling purchaser problem with additional side-constraints

The traveling purchaser problem (TPP) is the problem of determining a tour of a purchaser that needs to buy several items in different shops such that the total amount of travel and purchase costs is minimized. Motivated by an application in machine scheduling, we study a variant of the problem with additional constraints, namely, a limit on the maximum number of markets to be visited, a limit on the number of items bought per market and where only one copy per item needs to be bought. We present an integer linear programming (ILP) model which is adequate for obtaining optimal integer solutions for instances with up to 100 markets. We also present and test several variations of a Lagrangian relaxation combined with a subgradient optimization procedure. The relaxed problem can be solved by dynamic programming and can also be viewed as resulting from applying a state space relaxation technique to a dynamic programming formulation. The Lagrangian based method is combined with a heuristic that attempts to transform relaxed solutions into feasible solutions. Computational results for instances with up to 300 markets show that with the exception of a few cases, the reported differences between best upper bound and lower bound values on the optimal solutions are reasonably small.     

Online traveling salesman problem with deadline and advanced information

We consider the online version of the traveling salesman problem, where instances are not known in advance. Requests are released over time regardless whether the server is en route or not. This problem has been described as online TSP. Current literature about online TSP assumes that each request becomes known at its release time and will always remain active. We model the customers’ waiting psychology and service preparation time into the online TSP with the objective to serve as many requests as possible. More specifically, each request has a disclosure time before accepting service at its release time, and a deadline, which is no bigger than its release time plus the travel time from origin to its position. We give lower bounds for the competitive ratios, online algorithms, and quantify the influence of advanced information on competitive ratios.     

Solving a generalized traveling salesperson problem with stochastic customers

In this paper, a probabilistic generalized traveling salesperson problem (PGTSP) is introduced to address several applications. In the PGTSP, each customer belongs to a cluster that consists of a set of customers. Whether or not any given customer will be present during actual operations is known a priori only probabilistically. The PGTSP seeks the minimum expected length tour to visit a subset of all customers such that the tour traverses each cluster at least once. If when implementing the tour it is revealed that there is no demand for service within the cluster to which a customer stop belongs, that stop will be skipped. An exact solution algorithm based on the integer L-shaped method and three tour construction-based heuristics for quickly solving this problem are described in the paper. Computational experiments were conducted to assess computational requirements and solution quality of the proposed solution techniques. These experiments show that the exact method is able to solve small- and moderate-size problems to optimality. In addition, one of the proposed heuristics (the MMI heuristic), in particular, gives good approximate solutions (often a few percent from optimal) in very reasonable computational time.     

The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem

Traveling salesman problem (TSP) is proven to be NP-complete in most cases. The genetic algorithm (GA) is improved with two local optimization strategies for it. The first local optimization strategy is the four vertices and three lines inequality, which is applied to the local Hamiltonian paths to generate the shorter Hamiltonian circuits (HC). After the HCs are adjusted with the inequality, the second local optimization strategy is executed to reverse the local Hamiltonian paths with more than 2 vertices, which also generates the shorter HCs. It is necessary that the two optimization strategies coordinate with each other in the optimization process. The two optimization strategies are operated in two structural programs. The time complexity of the first and second local optimization strategies are O(n) and O(n³), respectively. The two optimization strategies are merged into the traditional GA. The computation results show that the hybrid genetic algorithm (HGA) can find the better approximate solutions than the GA does within an acceptable computation time.     

求解旅行商问题的整体优先算法

针对欧几里德旅行商问题,提出了一种“整体优先”算法。该算法的基本思路是边构造边调整路径,在调整中采用了独创的逆向调整方法,避免算法陷入局部优化陷阱。理论分析和大量实验结果表明,该算法不仅时间复杂度和空间复杂度低,寻优能力也相当强,其综合性能超过目前的一些主流算法。     

Sports tournament scheduling to determine the required number of venues subject to the minimum timeslots under given formats

We studied a two-phase, preliminary and finals, tournament, which commonly adopted for non-professional sports. The round robin tournament in divisions is played in the preliminary phase, followed by one of the three variants, namely single elimination, double elimination, and round robin in the finals phase. The objective is to determine the required number of venues (tables or courts) subject to the least timeslots under the given format. We used a diagonal symmetric matrix to pair teams to games and to schedule games in timeslots for the round robin tournament. For the preliminary phase, we proposed a procedure to find the number of divisions and the number of teams in each division that minimize the total number of games and timeslots accordingly. For the finals phase, we determined the number of venues required in the least timeslots. We then formulated a constraint programming model based on the diagonal symmetric matrix for the round robin tournament. Finally, we provided suggestions for choosing the appropriate competition format.     

The period traveling salesman problem: a new heuristic algorithm

A new, simple and effective heuristic algorithm has been developed for the period traveling salesman problem. Computational results obtained from the test problems taken from the literature indicate that the algorithm compares well in terms of accuracy with other existing algorithms, finding a larger number of best solutions. Moreover, its average percentage error and its worst ratio of solution to the best-known solution are smaller than those of the other existing algorithms.Scope and purposeIn the period traveling salesman problem, a traveling salesman must visit each city a fixed number of times over a given m-day planning period. Each city specifies a set of sequences of visit days and the visit days are assigned to the city by selecting one of these sequences. Moreover, for each day of the planning period, a not empty tour must be generated by connecting the salesman home city and the cities that must be visited on that day. The salesman objective is to minimize the total distance traveled over the entire m-day period. For this problem, arising in various situations such as mail delivery or lawn-care services, the paper proposes a simple and effective heuristic algorithm where an improvement procedure is embedded within a tour construction type procedure.     

考虑工作量平衡的多旅行商问题及其求解

根据多旅行商问题（MTSP）特点,针对最小化各旅行商最长路线这一优化目标,提出改进蚁群算法（IACO）。最小化各旅行商最长路线考虑各旅行商的工作量平衡,更具实际应用意义。算法中信息素更新与限制遵循最大最小蚁群算法（MMAS）框架,为提高算法性能设计混合局域搜索算法。利用文献中标准算例进行检验,结果表明,所设计蚁群算法与三种遗传算法相比表现出较强竞争性。     

The traveling purchaser problem,with multiple stacks and deliveries: A branch-and-cut approach

The Double Traveling Salesman Problem with Multiple Stacks is a pickup-and-delivery single-vehicle routing problem which performs all pickup operations before the deliveries. The vehicle has a loading space divided into stacks of a fixed height that follows a Last-In-First-Out policy. It has to collect products following a Hamiltonian tour in a pickup region, and then deliver them following a Hamiltonian tour in a delivery region. The aim is to minimize the total routing cost while satisfying the vehicle loading constraints.     

The multiple traveling purchaser problem for maximizing system’s reliability with budget constraints

The traveling purchaser problem (TPP) is a generalization of the well-known traveling salesman problem (TSP), which has many real-world applications such as purchasing the required raw materials for the manufacturing factories and the scheduling of a set of jobs over some machines, and many others. TPP also could be extended to the vehicle routing problem (VRP) by incorporating additional constraints such as multi-purchaser, capacity, distance and time restrictions. In the last decade, TPP has received some attention of the researchers in the operational research area. However it has not received the equivalent interest as much as TSP and VRP. Therefore, there does not exist a TPP study considering the reliability of components. The purpose of this paper is to introduce the ILP formulation for multiple TPP to maximize system’s reliability under budget constraint.     

The double traveling salesman problem with multiple stacks: A variable neighborhood search approach

The double traveling salesman problem with multiple stacks (DTSPMS) is a vehicle routing problem that consists on finding the minimum total length tours in two separated networks, one for pickups and one for deliveries. A set of orders is given, each one consisting of a pickup location and a delivery location, and it is required to send an item from the former location to the latter one. Repacking is not allowed, but collected items can be packed in several rows in such a way that each row must obey the LIFO principle. In this paper, a variable neighborhood search approach using four new neighborhood structures is presented to solve the problem.