Elise Miller-Hooks

Hao TangPhD in Civil Engineering and Operations Research, 2002
Penn State

Chief Data Scientist at Huawei Technologies Co., Ltd.
No. 2 Avenue National High-technical Property
Development Songshan Lake District, Dongguan 523808

Email: hao.tang1@huawei.com

Dissertation Title:

Routing Problems with Selection Decisions: Algorithms and Implementations


This dissertation addresses a class of routing problems in deterministic, stochastic or dynamic environments. The problems considered possess a common characteristic that only a select subset of all customers are included in solution tours. For this reason, 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.

The importance of vehicle routing-related problems has long been recognized due to the abundance of practical applications. 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). Most of these published works focus on deterministic routing problems, assuming that all customers must be visited. These works do not consider contexts where only a subset of all customers can be visited. However, in many real-world applications, not all considered customers can be included in solution tours due to practical limitations, e.g. vehicle capacity or tour duration limits. Moreover, the problems may be stochastic and/or dynamic in nature. Solution techniques derived solely from deterministic and static settings may not adequately address these stochastic and dynamic problems. 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 proposed routing problems have numerous applications in a variety of arenas. Through the proposed models and solution techniques, schedules that will result in better service and greater efficiency can be obtained. This will lead to improved customer satisfaction and reduced operational costs.

The first RPSD addressed is the PGTSP. The PGTSP is an extension of the Probabilistic Traveling Salesperson Problem (PTSP) and the Generalized Traveling Salesperson Problem (GTSP). Given a number of customer locations that are partitioned into a set of clusters, the PGTSP seeks the minimum expected length tour on a subset of all customer locations such that the tour traverses each cluster at least once and, in actual operations, those clusters with no realized demand are skipped. Potential applications of the PGTSP include, among others, routing aircraft for overnight delivery, analyzing travel behavior in trip-chaining activities and modeling the probabilistic traveling buyer’s problem. Exact and heuristic solution procedures are developed for the PGTSP and related properties are derived. 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. The objective of the SSTSP is to determine an a priori maximum profit tour such that the likelihood that the total actual tour duration on a given day exceeds a given threshold is less than a chosen probability value. Potential applications include service scheduling over a geographic region, the orienteering problem and scheduling a recruiter for recruiting football team members. An exact branch-and-cut algorithm and a construct-and-adjust heuristic are proposed to solve the SSTSP. Numerical experiments are conducted to assess the effectiveness of these solution procedures. 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. This extends the concepts of the STSP with deterministic service times to multiple tours (i.e. vehicles). Unlike the classical VRP, the SVRP does not require that all customers under consideration be included in solution tours and its goal is to construct a set of tours that maximize total collected rewards received from visiting customers. Applications considered in the literature include home fuel delivery, the team orienteering problem, and a special class of pickup/delivery problems with high volume of requests. A tabu search heuristic is developed to solve the problem. The effectiveness of the proposed tabu search approach is examined on a set of benchmark problems through comparisons of solution quality with other existing heuristic solution techniques for the SVRP. 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. This problem is illustrated through a real-world scheduling application identified by a large international firm. The tabu search heuristic developed for the static SVRP is modified to address this time-dependent SVRP. 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.

Top of Page

Elise Miller-Hooks, Ph.D.
Bill & Eleanor Hazel Chair in Infrastructure Engineering

Phone: 703.993.1685
Email: miller@gmu.edu

Office: 4614 Nguyen Engineering Building

Sid and Reva Dewberry Department of Civil, Environmental and Infrastructure Engineering
George Mason University
4400 University Drive, MS 6C1
Fairfax, VA 22030


Additional Resources




Volgenau School of Engineering
George Mason University