Routing problems with selection decisions: Algorithms and implementations.

摘要

This dissertation addresses a class of routing problems in deterministic, stochastic or dynamic environments. These problems are referred to as Routing Problems with Selection Decisions (RPSDs). Specifically, as part of this work, problem formulations and solution procedures to the Probabilistic Generalized Traveling Salesperson Problem (PGTSP), Selective Traveling Salesperson Problem with Stochastic Service Times (SSTSP), Selective Vehicle Routing Problem (SVRP) and Selective Vehicle Routing Problem with Time-Dependent Rewards (SVRPTD) are posed.; In the past several decades, an enormous number of works have been published to address a variety of routing problems, including the well-known Traveling Salesperson Problem (TSP) and Vehicle Routing Problem (VRP). The main motivation of this dissertation is due to the importance of the applications for the RPSDs and the gap that exists in the literature. Specifically, the primary contributions of this work include: (1) mathematical formulations for the addressed RPSDs; (2) exact algorithms for solving the PGTSP and the SSTSP; (3) heuristics (greedy and metaheuristic) for solving the four considered RPSDs; and (4) implementation of a tabu search heuristic for the SVRPTD on a large real-world service scheduling problem.; The first RPSD addressed is the PGTSP. Numerical experiments conducted on randomly generated problem instances show that the exact algorithm based on the integer L-shaped method can solve small- and moderate-size problems to optimality and a greedy insertion heuristic is able to provide competitive approximate solutions with limited computational effort.; The second problem addressed in this dissertation is the SSTSP, where customer service times are known a priori only probabilistically. Results from these experiments show that the exact algorithm is able to solve small- and moderate-size problems to optimality and the heuristic can obtain near-optimal solutions efficiently.; The third RPSD studied is the SVRP, where, instead of imposing capacity constraints as in the classical VRP, vehicle tours are subject to tour duration (or length) limits. The experiments indicate that the tabu search heuristic proposed in this dissertation outperforms other published heuristics in the literature.; The last RPSD addressed is the SVRPTD, an extension to the static SVRP, where rewards collected by servicing customers are time-dependent. Numerical experiments conducted on the data sets derived for this considerably large-size real-world application show that the proposed tabu search is able to provide close to optimal solutions for this problem in reasonable computational effort. (Abstract shortened by UMI.)