Solving the p-median problem with pos/neg weights by variable neighborhood search and some results for special cases

The p-median problem with positive and negative weights has been introduced by Burkard and Krarup [Computing 60 (1998) 193]. In this paper we discuss some special cases of this problem on trees and propose a variable neighborhood search procedure for general networks, which is in fact a modification of the one proposed by Hansen and Mladenovic [Locat. Sci. 5 (1997) 207] for the p-median. We also compare the results with those obtained by a Tabu search procedure.     

Solving the unconstrained optimization problem by a variable neighborhood search

This paper presents variable neighborhood search (VNS) for the problem of finding the global minimum of a nonconvex function. The variable neighborhood search, which changes systematically neighborhood structures in the search for finding a better solution, is used to guide a set of standard improvement heuristics. This algorithm was tested on some standard test functions, and successful results were obtained. Its performance was compared with the other algorithms, and observed to be better.     

A gamma heuristic for the p-median problem

Heuristic concentration (HC) is a two-stage metaheuristic that can be applied to a wide variety of combinatorial problems. It is particularly suited to location problems in which the number of facilities is given in advance. In such settings, the first stage of HC repeatedly applies some random-start interchange (or other) heuristic to produce a number of alternative facility configurations. A subset of the best of these alternatives is collected and the union of the facility sites in them is called a concentration set (CS). Among the component elements of the CS are likely to be included those sites which are members of the optimal solution. In earlier studies the second stage of HC has consisted of an exact procedure to extract the best possible solution from the CS. In this paper we demonstrate, for the p-median problem, the use of two sequentially active heuristics in the second stage of HC. That is, we offer two additional layers of heuristics to improve solutions which are found in the first stage of HC. Thus we are describing a variant of the HC metaheuristic consisting of three layers of heuristics which are utilized in sequence. We propose for this procedure the name of Gamma Heuristic.     

A variable neighborhood search for the network design problem with relays

Given a set of commodities to be routed over a network, the network design problem with relays involves selecting a route for each commodity and determining the location of relays where the commodities must be reprocessed at certain distance intervals. We propose a hybrid approach based on variable neighborhood search. The variable neighborhood algorithm searches for the route for each commodity and the optimal relay locations for a given set of routes are determined by an implicit enumeration algorithm. We show that dynamic programming can be used to determine the optimal relay locations for a single commodity. Dynamic programming is embedded into the implicit enumeration algorithm to solve the relay location problem optimally for multiple commodities. The special structure of the problem is leveraged for computational efficiency. In the variable neighborhood search algorithm, the routes of the current solution are perturbed and reconstructed to generate neighbor solutions using random and greedy construction heuristics. Computational experiments on three sets of problems (80 instances) show that the variable neighborhood search algorithm with optimal relay allocations outperforms all existing algorithms in the literature.     

A modified variable neighborhood search for the discrete ordered median problem

This paper presents a modified Variable Neighborhood Search (VNS) heuristic algorithm for solving the Discrete Ordered Median Problem (DOMP). This heuristic is based on new neighborhoods’ structures that allow an efficient encoding of the solutions of the DOMP avoiding sorting in the evaluation of the objective function at each considered solution. The algorithm is based on a data structure, computed in preprocessing, that organizes the minimal necessary information to update and evaluate solutions in linear time without sorting. In order to investigate the performance, the new algorithm is compared with other heuristic algorithms previously available in the literature for solving DOMP. We report on some computational experiments based on the well-known N-median instances of the ORLIB with up to 900 nodes. The obtained results are comparable or superior to existing algorithms in the literature, both in running times and number of best solutions found.     

An exact algorithm for the fuzzy p-median problem

In this paper we propose a fuzzy version of the classical p-median problem. We consider a fuzzy set of constraints so that the decision-maker will be able to take into account solutions which provide significantly lower costs by leaving a part of the demand uncovered. We propose an algorithm for solving the problem which is based on Hakimi's works and we compare the crisp and the fuzzy approach by means of an example.     

A branch-and-cut method for the obnoxious p-median problem

The obnoxious p-median (OpM) problem is the repulsive counterpart of the ore known attractive p-median problem. Given a set I of cities and a set J of possible locations for obnoxious plants, a p-cardinality subset Q of J is sought, such that the sum of the distances between each city of I and the nearest obnoxious site in Q is maximised. We formulate (OpM) as a {0,1} linear programming problem and propose three families of valid inequalities whose separation problem is polynomial. We describe a branch-and-cut approach based on these inequalities and apply it to a set of instances found in the location literature. The computational results presented show the effectiveness of these inequalities for (OpM). The work of the first author has been partially supported by the Coordinated Project C.A.M.P.O. and that of the third author by a short mobility grant, both of the Italian National Research Council.     

A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem

We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman’s tour and designing the optimal travelling salesman’s tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers.     

Two exact algorithms for the capacitated p-median problem

The p-median problem has been widely studied in combinatorial optimisation, but its generalisation to the capacitated case has not. We propose a branch and price algorithm, comparing it with a standard MIP solver and a branch and bound algorithm based on Lagrangean relaxation. We present computational experience, using test instances drawn from the literature and new instances with higher ratio between the number of medians p and the number of nodes N. The branch and price algorithm shows very good performances and computational time robustness in solving problems for any ratio.Received: December 2002, Revised: August 2003AMS classification: 90C10, 90C27     

A variable neighborhood search for the capacitated arc routing problem with intermediate facilities

The capacitated arc routing problem (CARP) focuses on servicing edges of an undirected network graph. A wide spectrum of applications like mail delivery, waste collection or street maintenance outlines the relevance of this problem. A realistic variant of the CARP arises from the need of intermediate facilities (IFs) to load up or unload the service vehicle and from tour length restrictions. The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the basic problem as well as its extensions. The VNS shows excellent results on four different benchmark sets. Particularly, for all 120 instances the best known solution could be found and in 71 cases a new best solution was achieved.     

Hybrid scatter search and path relinking for the capacitated p-median problem

In this paper we propose heuristic algorithms for the capacitated p-median problem. In the first one solutions are obtained with Scatter Search whereas the second algorithm uses Path Relinking. A third approach that combines Path Relinking with Scatter Search is also analyzed. The GRASP methodology is used to generate the initial Reference Set both for Scatter Search and Path Relinking. Computational experiments have been carried out with different data sets in order to evaluate the performance of the approaches. In general, Scatter Search outperforms Path Relinking, but the use of Path Relinking prior to Scatter Search has shown to enhance the performance of Scatter Search, specially in terms of the computation times required, due to the improvement of the initial Reference Set. The obtained results, that have been compared with previous approaches, show the efficiency of the methods both in terms of the quality of the solutions found and of the required computation times, even for very large instances.     

Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs

In this paper, we present an algorithm for solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs. The path cost function considered is comprised of two attributes, travel time and toll, that are combined into a nonlinear generalized cost. Travel demand is determined endogenously according to a travel disutility function. Travelers choose routes with the minimum overall generalized costs. The algorithm involves two components: a bicriteria shortest path routine to implicitly generate the set of non-dominated paths and a projection and contraction method to solve the nonlinear complementarity problem (NCP) describing the traffic equilibrium problem. Numerical experiments are conducted to demonstrate the feasibility of the algorithm to this class of traffic equilibrium problems.     

A general variable neighborhood search variants for the travelling salesman problem with draft limits

In this paper, we present two general variable neighborhood search (GVNS) based variants for solving the traveling salesman problem with draft limits (TSPDL), a recent extension of the traveling salesman problem. TSPDL arises in the context of maritime transportation. It consists of finding optimal Hamiltonian tour for a given ship which has to visit and deliver products to a set of ports while respecting the draft limit constraints. The proposed methods combine ideas in sequential variable neighborhood descent within GVNS. They are tested on a set of benchmarks from the literature as well as on a new one generated by us. Computational experiments show remarkable efficiency and effectiveness of our new approach. Moreover, new set of benchmarks instances is generated.     

带投资约束且p不确定的推广p-中位问题

p-中位问题是设施选址中的一个经典模型,在交通、物流等领域有着广泛应用．在经典p-中位问题的基础上提出一种p不确定的推广p-中位问题,并且加上总投资约束,使得此推广模型更加实用．针对此推广模型,提出三种启发式算法：简单启发式算法、变邻域搜索算法和改进的遗传算法．数值实验结果表明变邻域搜索算法和改进的遗传算法在求解此推广模型时是有效的．