(234d) Exact Optimization Frameworks for Time-Consistent Distribution

In the context of optimizing distribution operations, the recent trend calls for shifting the focus from merely managing the distribution fleet towards a more explicit focus on improving service quality.  Moreover, it is relatively common in practice for the distributor to provide repetitive service to customers along a multi-period time horizon. In such settings, a distributor may add value to its business by committing to consistent delivery times across the planning horizon. Doing so exposes efficiencies that reduce costs for both the distributor and the customer (e.g., by reducing the need for committing loading-dock resources) and can give the service provider significant competitive advantages. Several applications adopt such consistent service policies, including the Vendor-Managed Inventory distribution schemes that are prevalent in the chemical industries.

All previous approaches to address time-consistent vehicle routing problems [1-3] have been heuristic in nature, without providing any mathematical guarantee on solution quality. In this work, we present two exact solution approaches to address such a problem. More specifically, we study the so-called Consistent Traveling Salesman Problem (ConTSP) [4] in which one aims to design minimum-cost (or, minimum makespan) routes over a finite, multi-period horizon so as to serve a set of customers with known demands and service durations using a single vehicle. Customers may require service in only one time period (typically, residential or small customers) or over multiple periods (typically, commercial or large customers). In general, since a customer may or may not require service in a given time period, only a subset of customers need to be visited in each period. The consistency requirement applies to every customer that requires service in more than one time period, i.e., every such customer must be visited at roughly the same time in each period where service is required. This is formally imposed by requiring that the difference between the earliest and latest vehicle arrival times (along the time horizon) at each customer location does not exceed a limit. In practice, this limit may be set by either the customer or by the service provider.

Our first approach is based on a branch-and-cut framework. In this approach, we develop three alternative MILP formulations, and compare their performance when serving as the basis for a branch-and-cut solution algorithm. To this end, we develop a new family of cutting planes for the ConTSP, which we call “Inconsistent Path Elimination Constraints,” and we describe an effective way to separate them in polynomial time. We also discuss how TSP cutting planes [5] can be used in this context to complement the newly proposed cuts, but we show via polyhedral analysis that, unlike the case of TSP, the TSP cutting planes do not constitute facets of the ConTSP polytope. A numerical study on a comprehensive collection of benchmark instances, which we developed by extending well-known TSPLIB datasets, shows that a formulation involving only binary arc variables and an exponential number of constraints is the computationally most efficient MILP model.

Our second approach is based on a decomposition of the multi-period problem into a sequence of single-period routing problems. More specifically, we describe a scheme to decompose the problem into single period TSPs with arrival time windows for each customer. Consistency is enforced implicitly by dynamically tightening these time windows in a branch-and-bound implementation with separable branching rules. A numerical study shows that this approach is computationally competitive to the branch-and-cut framework, while in addition, it is able to accommodate waiting times at each customer location.

Using our approaches, we have been able to solve to guaranteed optimality problems with 100 customers requiring service over a 3-period horizon, problems with 75 customers over a 5-period horizon and problems with 50 customers over a 7-period horizon. Furthermore, we estimate the “price of consistency,” which is the additional cost that a distributor must incur, on average, in order to implement consistent delivery schedules. Our results show that often the additional costs are modest and, therefore, consistency of service is a value proposition that distributors should look into further.

References:

[1] C. Groër, B. Golden, and E. Wasil (2009). The Consistent Vehicle Routing Problem. Manufacturing & Service Operations Management, 11(4):630–643.

[2] C. D. Tarantilis, F. Stavropoulou, and P. P. Repoussis (2012). A template-based Tabu Search algorithm for the Consistent Vehicle Routing Problem. Expert Systems with Applications, 39(4):4233–4239.

[3] A. A. Kovacs, B. L. Golden, R. F. Hartl and S. N. Parragh (2014). Vehicle routing problems in which consistency considerations are important: A survey. Networks, 64(3):192–213.

[4] A. Subramanyam, C. E. Gounaris (2015). A Branch-and-Cut Framework for the Consistent Traveling Salesman Problem. Under review.

[5] D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook (2007). The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press, USA.