Shortest path - capacitated maximum covering problems.

摘要

I study the shortest path - capacitated maximum covering problem (SP-CMCLP). Current, ReVelle and Cohon (1985) first studied the un-capacitated version of this problem. The two objectives of the problem are the minimization of the path length from a predetermined starting node to a predetermined terminal node and the maximization of the total demand covered by the facilities located at the nodes in the path. They solved a special case in which a demand can be covered only if it is located on the path. I solve the general model. I also introduce facility capacity constraints, new algorithms and new demand coverage structures to this problem.;I decompose the problem into a k-shortest path problem (kSP) and a capacitated maximum covering problem (CMCLP). The k-shortest path problem is solved by a path deletion algorithm (refer to Azevedo, et al., 1993, 1994). The capacitated maximum covering problem is solved by various heuristics and meta-heuristics including lagrangian relaxation, two versions of Tabu search and a simulated annealing method.;To the knowledge of the author, the Tabu search and simulated annealing methods introduced are the first meta-heuristics developed for the capacitated maximum covering problem. In these meta-heuristics, I use four neighborhood structures. These are (1) one-interchange which exchanges an selected facility with an unselected facility, (2) client shift which shifts a satisfied demand from one selected facility to another selected facility, (3) demand swap (or demand reallocation) which swaps one (or more) assigned demand node (nodes) with one (or more) unassigned demand node (nodes) within the coverage distance of a selected facility site, (4) demand addition which adds one or more unassigned demand to a selected facility. These neighborhoods are at different levels and are used in different stages of the meta-heuristics. I design an embedded meta-heuristic procedure which has inner loops of single neighborhoods and an outer loop of multiple alternate inner loops for different neighborhoods. I design a heuristic method and a penalty method for the demand allocation sub-problem in the embedded Tabu search. In the penalty method, I use surrogate relaxation and add a penalty term to the objective function for the violated capacity constraints. An embedded simulated annealing method with temperature vibration is also designed using heuristic demand allocation.;I also solve a new version of the shortest path - capacitated maximum covering problem with tree coverage structure (SP-CMCLP-TREE). Demand is supplied by sub-paths on a minimum spanning tree constructed from an underlying network. A demand is counted as covered if the total arc length of a path from the demand to a facility site is within coverage distance and the demand can be satisfied only if all the intermediate demand nodes on the path are satisfied.;Computational results for networks selected from literature show the effectiveness of the heuristics designed. Tabu search performs the best in solution quality, while Lagrangian relaxation and simulated annealing generate solutions of satisfactory quality using less time. Different path-coverage structures are used based on the properties of the networks. Tree demand coverage structure works better than traditional coverage structure for large partial networks. The impact of different network parameters are also studied.