2022 Annual Meeting

(625c) Workload Balancing in Periodic Distribution Scheduling and Routing Optimization

Authors

Izadkhah, A. - Presenter, CARNEGIE MELLON UNIVERSITY
Gounaris, C., Carnegie Mellon University
Laínez-Aguirre, J. M., University of Buffalo
Pinto, J. M., Linde plc
Wang, A., Carnegie Mellon University
Industrial gases companies often operate a massive supply chain network, with last mile delivery being one of its most important aspects. Therefore, careful planning of last mile delivery operations is extremely important for overall business profitability. Besides classical focus on limiting routing costs, other factors such as balancing the daily load to be served are often viewed as equally important objectives [1]. Usually, it is very typical in the industrial gases context that some clients have a vendor-managed inventory agreement such that the distributor maintains some level of control on when to deliver product under the condition that inventories are maintained between acceptable levels. To that end, the vendor designs a periodic visiting plan for these clients specifying the frequency of visit and delivered demand. In the literature, this problem setting is known as the Periodic Vehicle Routing Problem with Service Choice (PVRPSC) [2]. In the archetypal PVRPSC, the emphasis is only on minimizing the routing costs. Whereas exclusive focus on this objective might result in schedules that are very efficient in terms of routing, it usually creates a very uneven load for distribution, where some days are extremely burdensome whereas other days require only very little effort to execute. In this work, we are trying to address this issue by co-optimizing load distribution levels within PVRPSC.

In the literature, there are numerous studies that tackled different types of balancing considerations such as route length [3, 4], arrival times [5], or served demand [6], in conjunction with designing cost-effective routes. Interested readers are referred to [1] for a comprehensive review on this topic. It is important to note that the majority of these works considered single period routing problems and there are only a few studies that tackle balancing and equity in context of multi-period routing. In [7], the authors considered workload balancing in terms of number of customers visited by each vehicle in the PVRP setting. Another equity approach was used by authors of [8] in which they minimized the length of the longest route along with routing costs in a variant of PVRP. A notable example is the study of [9] where the problem of last-mile dispatching with stochastic demands is considered with emphasis on workload equity by balancing the delivery amounts and durations across a short- and long-term planning horizon. In our work, we will consider workload as total amount of served demand on each day of the planning horizon in context of PVRPSC.

In principle, incorporating workload balancing in a vehicle routing setting leads to a multi-objective optimization problem, which can generally be addressed via the well-known epsilon constraint method [10]. The problem itself can be cast as a set-partitioning model and solved via purpose-built exact methods (e.g. [11, 12]). We specifically employ a branch-price-and-cut solution strategy that we tailor to this specific problem, introducing also several strengthening inequalities to further improve the lower bound. We evaluate our workload balancing PVRPSC framework on benchmark instances we generated from classic PVRP instances from the literature as well as on real-life industrial datasets provided by Linde. Our preliminary computational studies confirm the success of our framework in co-optimizing workload balancing and routing.

[1]. Matl, P., Hartl, R.F. and Vidal, T., 2018. Workload equity in vehicle routing problems: A survey and analysis. Transportation Science, 52(2), pp.239-260.

[2]. Francis, P., Smilowitz, K. and Tzur, M., 2006. The period vehicle routing problem with service choice. Transportation science, 40(4), pp.439-454.

[3]. Jozefowiez, N., Semet, F. and Talbi, E.G., 2002, September. Parallel and hybrid models for multi-objective optimization: Application to the vehicle routing problem. In International Conference on Parallel Problem Solving from Nature (pp. 271-280). Springer, Berlin, Heidelberg.

[4]. Reiter, P. and Gutjahr, W.J., 2012. Exact hybrid algorithms for solving a bi-objective vehicle routing problem. Central European Journal of Operations Research, 20(1), pp.19-43.

[5]. Golden, B.L., Kovacs, A.A. and Wasil, E.A., 2014. Chapter 14: Vehicle Routing Applications in Disaster Relief. In Vehicle Routing: Problems, Methods, and Applications, Second Edition (pp. 409-436). Society for Industrial and Applied Mathematics.

[6]. Kritikos, M.N. and Ioannou, G., 2010. The balanced cargo vehicle routing problem with time windows. International Journal of Production Economics, 123(1), pp.42-51.

[7]. Gulczynski, D., Golden, B. and Wasil, E., 2011. The period vehicle routing problem: New heuristics and real-world variants. Transportation Research Part E: Logistics and Transportation Review, 47(5), pp.648-668.

[8]. Liu, R., Xie, X. and Garaix, T., 2013, April. Weekly home health care logistics. In 2013 10th IEEE international conference on networking, sensing and control (ICNSC) (pp. 282-287). IEEE.

[9]. Wang, Y., Zhao, L., Savelsbergh, M. and Wu, S., 2022. Multi-Period Workload Balancing in Last-Mile Urban Delivery. Transportation Science.

[10]. Laumanns, M., Thiele, L. and Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. European Journal of Operational Research, 169(3), pp.932-942.

[11]. Sarpong, B.M., Artigues, C. and Jozefowiez, N., 2013, September. Column generation for bi-objective vehicle routing problems with a min-max objective. In ATMOS-13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems-2013 (Vol. 33, pp. 137-149). Schloss Dagstuhl―Leibniz-Zentrum fuer Informatik.

[12]. Huang, M., Smilowitz, K. and Balcik, B., 2012. Models for relief routing: Equity, efficiency and efficacy. Transportation research part E: logistics and transportation review, 48(1), pp.2-18.