Approximating the Length of Vehicle Routing Problem Solutions Using Complementary Spatial Information




Mei, Xi

Journal Title

Journal ISSN

Volume Title



Accurately estimating the length of the Vehicle Routing Problem (VRP) distances is useful for transportation planning. This study extends the work of previous research where multiple linear regression models were used to estimate the average distance of the VRP solutions with various customer demands and capacity constraints. This research expands on that approach in three ways: first, the point patterns used here to assist in estimation have a wider range of customer clustering or dispersion values as measured by the Average Nearest Neighbor Index (ANNI) rather than using only a Poisson point process or random point process; second, the tour coefficient adjusted by complementary spatial information yielded statistically more accurate estimations; third, the VRP solutions length approximation was used to compare the pattern of customer locations in both planar continuous space and network space. To generate a full range of ANNI values, point patterns were simulated using a Poisson process, a Matern clustering process, and a Simple Sequential Inhibition process to obtain random, clustered, and dispersed point patterns, respectively. The coefficients of independent variables in the models were used to explain how the spatial distributions of customers influence the VRP distances. Finally, the bulky waste collection problem in Fairfax County, Virginia, was analyzed and used as a case study for this research. The spatial statistics applied to the network space from the case study have the advantage of using the network nearest average neighbor index. In summary, this study approached the VRP approximation problem by using distinct spatial variations, incorporating geographic indices and distance measures, and modeling the process in a real world network in Fairfax, VA.



Geography, Operations research, Point process, Spatial statistics, VRP Approximation