Precedence-Constrained Colored Traveling Salesman Problem An Augmented Variable Neighborhood Search Approach
ABSTARCT :
A traveling salesman problem (CTSP) as a generalization of the well-known multiple traveling salesman problem utilizes colors to distinguish the accessibility of individual cities to salesmen. This work formulates a precedence-constrained CTSP (PCTSP) over hypergraphs with asymmetric city distances. It is capable of modeling the problems with operations or activities constrained to precedence relationships in many applications. Two types of precedence constraints are taken into account, i.e., 1) among individual cities and 2) among city clusters. An augmented variable neighborhood search (VNS) called POPMUSIC-based VNS (PVNS) is proposed as a main framework for solving PCTSP. It harnesses a partial optimization metaheuristic under special intensification conditions to prepare candidate sets. Moreover, a topological sort-based greedy algorithm is developed to obtain a feasible solution at the initialization phase. Next, mutation and multi-insertion of constraint-preserving exchanges are combined to produce different neighborhoods of the current solution. Two kinds of constraint-preserving k-exchange are adopted to serve as a strong local search means. Extensive experiments are conducted on 34 cases. For the sake of comparison, Lin-Kernighan heuristic, two genetic algorithms and three VNS methods are adapted to PCTSP and fine-tuned by using an automatic algorithm configurator-irace package. The experimental results show that PVNS outperforms them in terms of both search ability and convergence rate. In addition, the study of four PVNS variants each lacking an important operator reveals that all operators play significant roles in PVNS.
EXISTING SYSTEM :
? A characteristic of the BPP is existence of large plateaus (many different configurations, in terms of assignment of items to bins, correspond to the same number of bins), an auxiliary objective function is introduced, i.e., maximization of the sum of squared slacks of the bins.
? Initial solutions for VNS are obtained by modification of an existing one (called MBS’), which already produces good solutions.
? The well-known simple plant location problem (SPLP) is to locate facilities among a given set of cities in order to minimize the sum of set-up costs and distribution cost from the facilities to a given set of users, whose demand must be satisfied.
? It is an interchange heuristic, where points are reassigned to another cluster than their own, one at a time, until a local optimum is reached.
DISADVANTAGE :
? The optimization of delivery tours is usually modeled as a Traveling Salesman Problem (TSP).
? The Time-Dependent Traveling Salesman Problem (TDTSP) is the extended version of the Traveling Salesman Problem (TSP) where arc costs depend on the time when the arc is traveled.
? When this constraint is taken into consideration the problem is called TDTSP with Time-Windows (TDTSPTW).
? The Traveling Salesman Problem (TSP) is an NP-hard problem and one of the most studied problems in combinatorial optimization as it appears as a substructure in many problems but also has several applications in its pure form.
? It is more flexible than Local Search for complex problems involving many types of constraints and resources.
PROPOSED SYSTEM :
• A Multi-level TS is proposed in for solving the Continuous min–max problem, where each level represents a ball of different size in the vicinity of the current solution, i.e., different neighborhoods, and a tabu list is constructed for each level.
• In repeating a sequence of four proposed local searches, the information on unsuccessful pairs of edges is memorized so that in the next repetition those pairs are not considered.
• A metaheuristic approach that combines VNS and TS and uses several neighborhood structures is proposed in.
• In two operators which make use of Constraint programming and local search to explore their neighborhood are proposed.
ADVANTAGE :
? It is important to develop a solving method flexible enough to integrate other constraints in the main model without hindering performances and ideally in a simple way.
? They compare the four different strategies on a number of performance measures, that can be summed up by: number of vehicles, total duty time, total traveled distance and total late time at customers.
? The goal is to have the best ratio between time complexity and filtering efficiency and, of course, the cost of calls of the filtering algorithms at each node must be less than the time required by the search procedure to exclude the same values by testing.
? In the same way, this constraint can be used to model the TSP by constraining the visits performed by the same salesperson to happen in a sequence.
|