The vehicle routing problem (VRP) in support of less-than-truckload (LTL) city operations has been well studied in the research literature, but the applicability of such methods is hampered by the uncertainty associated with the customer base. This topic is the focus of this dissertation. The problem described is the citywide LTL (CLTL) problem, where operations consist of deterministic deliveries on outbound moves from a depot followed by pick-ups on inbound moves returning to the depot. This type of stochastic vehicle routing problem (SVRP) is classified as a VRP with stochastic demands and customers with backhauls (VRPSDCB), which has not been previously studied.; This dissertation utilizes a heuristic solution of a deterministic version of the problem, where various strategies are used to identify desirable subsets of customers with stochastic demand for inclusion into initial route generation decisions. The stochastic pickup customers not involved in the initial route generation are referred to as “excluded customers.” In this method, all deterministic customers (which includes all delivery customers and some pickup customers) and some subset of stochastic customers are initially routed by deterministic models. Then, each excluded customer is inserted into existing routes via greedy selection based on distance.; The primary contributions of this work are first, the generalization of the vehicle routing problem with stochastic demands and customers (VRPSDC) to include two customer types. The second is the use of exclusion strategies to reduce a complicated SVRP to a more tractable deterministic problem that increases the size of problems that may be considered. Experimental results indicate with statistical significance that choice of routing algorithm and exclusion strategy affect total distance traveled by all vehicles, required number of vehicles, and the difference between planned distance and total distance traveled.; The technique proposed was tested against post priori deterministic optimal solutions and performed well. This indicates through an objective measure that the exclusion heuristic is worthy of further study. With the best combination of algorithm and exclusion policy, solutions found for the three problems tested resulted in percentage deviations from optimality of approximately 2%, 1%, and 2% greater than the objective value of a deterministic optimal solution. Also, the proposed exclusion technique results in statistically better solutions than that obtained by use of an approach that disregards any stochastic customers.
展开▼
