Long-Term Optimal Delivery Planning for Replacing the Liquefied Petroleum Gas Cylinder

Akihiro Yoshida, Haruki Sato, Shiori Uchiumi, Nariaki Tateiwa, Daisuke Kataoka, Akira Tanaka, Nozomi Hata, Yosuke Yatsushiro, Ayano Ide, Hiroki Ishikura, Shingo Egi, Miyu Fujii, Hiroki Kai, Katsuki FujisawaarXiv 2021 · OpenReview

TL;DR

This paper tackles the complex problem of optimizing liquefied petroleum gas (LPG) cylinder replacement logistics. By integrating smart meter data for more accurate gas consumption forecasting and employing a multi-step optimization approach, their system significantly reduces gas shortages, unnecessary visits, and overall delivery time, demonstrating a practical application of advanced optimization in a real-world service industry.

What Problem Does This Paper Address?

The traditional process of replacing LPG cylinders relies on manual checks, leading to frequent, often unnecessary, customer visits and a risk of gas shortages. Determining the exact remaining gas level without a physical inspection is challenging. While smart meters offer a solution by providing daily consumption data, integrating this data into an efficient, long-term delivery plan that considers factors like customer risk, delivery routes, and staff availability is a significant logistical puzzle. This paper addresses the "Cylinder Replacement Problem" (CRP), aiming to create an optimal plan that minimizes gas shortages and operational costs.

Methods

The proposed solution is a three-step system:

  1. Estimating Replacement Date:
    • For smart meter customers, daily gas consumption is directly available.
  2. For conventional meter customers, gas usage is extrapolated using a novel k-nearest neighbor (kNN) approach that leverages data from similar smart meter customers. This is a key innovation for handling legacy infrastructure.
  3. A risk function is then defined to quantify the "emergency" of a gas shortage, considering forecast gas usage and its uncertainty. This function categorizes customers into high, moderate, and low-risk groups.
  4. Acquiring Customer Lists for Multiple Dates:
    • This step aims to create a customer list for replacement, prioritizing high-risk customers and considering moderate-risk ones to prevent future shortages and smooth out daily workloads.
  5. A bounding-box based model is used to define a rectangular area covering customers needing replacement. This is optimized to minimize the area, thus potentially reducing travel distance.
  6. A multi-period optimization model is employed to simultaneously acquire lists for multiple days, preventing the concentration of deliveries on specific days and avoiding large delivery areas that could impact future routes.
  7. Determining Delivery Route:
    • This involves two sequential optimization problems:
  8. Maximizing Deliveries: Prioritizes visiting moderate-risk customers while ensuring high-risk customers are served, aiming to maximize the number of deliveries.
  9. Minimizing Working Duration: Once the set of customers to visit is determined, this step optimizes the order of visits to minimize the total travel and service time.
  10. The actual route optimization between customers is handled by an external service (MapBox), focusing the paper's contribution on the planning and ordering aspects.

Datasets

  • Real-world data from over 1,000 LPG customers in Chiba prefecture, Japan, was used for a large-scale field test.
  • This dataset included both customers with smart meters and those with conventional meters.
  • For numerical experiments in the appendix, data was generated by intentionally omitting smart meter readings to simulate conventional meter behavior.

Key Insights and Ideas

  • Bridging the Smart Meter Gap: The kNN-based extrapolation of gas usage for conventional meters is a crucial innovation, allowing the system to provide benefits even when not all customers have smart meters.
  • Proactive Risk Management: The risk function, which considers forecast uncertainty, allows for proactive replacement scheduling, preventing shortages and smoothing demand.
  • Multi-Day Planning: Simultaneously planning for multiple days, rather than sequentially, is key to optimizing delivery routes and preventing future logistical bottlenecks.
  • Bounding Box Optimization: Using a bounding box to cover customers, without necessarily including the depot, leads to more efficient delivery routes, especially when the depot is geographically distant from customer clusters.

Key Results

A large-scale field test with over 1,000 customers demonstrated significant improvements:

  • Zero gas shortages were reported during the test period.
  • Nonreplacement visits (visits where no replacement was needed) were reduced to zero.
  • Average travel time per day was reduced by approximately 20% (from 2h 52m to 2h 06m).
  • Average travel time per customer was reduced by about 36% (from 3m 46s to 2m 34s).
  • The system achieved these improvements even with a significant portion of customers (about one-third) not having smart meters.
  • Experimental results showed that the proposed system outperformed the gas provider's existing methods across various metrics, including success rate and fail-over events.

Limitations and Future Work

  • Smart Meter Adoption: The system's effectiveness is enhanced by smart meters, and the paper acknowledges that wider adoption will further improve gas shortage prediction.
  • Customer Aggregation: Feedback suggests that grouping customers for replacement more effectively (e.g., those in close proximity) could further reduce workload. This is identified as a key area for future research.
  • Customer Prioritization for Smart Meters: Determining which customers should be prioritized for smart meter installation is another avenue for future work to maximize the impact of the system.
  • Generalization to Other Industries: The framework's potential application to other delivery-based industries (e.g., grocery delivery) is highlighted as a future direction.
  • Hyperparameter Sensitivity: While experiments explored parameter tuning, further refinement of parameters like qhigh and qmdr could potentially improve results.

Summary updated

Abstract

In the daily operation of liquefied petroleum gas service, gas providers visit customers and replace cylinders if the gas is about to run out. For a long time, frequent visits to customers were required because they could not determine the amount of remaining gas without a staff visit and observation. To solve this problem, smart meters are started to be employed to acquire gas consumption more frequently without visiting customers. In this study, we construct a system to optimize plans for cylinder replacement, and evaluate it with a large-scale field test. We propose an algorithm to create a replacement plan with three steps: estimating the replacement date, acquiring the customer list for replacement, and determining the delivery route. A more accurate estimation of the replacement date can be acquired with a smart meter, which is used for making a customer list for replacement. The formulation for making a customer list enables the gas provider to replace cylinders some days before the date when the gas would run out. It can suppress the concentration of replacements on certain days. Large-scale verification experiments were performed with more than 1,000 customers in Chiba prefecture in Japan. In the field test, the gas provider incorporated the system into its replacement operations. Moreover, the replacement plans developed by the proposed system were compared with that by the gas provider. Our system reduced the number of gas cylinders with gas shortage, the number of visits without replacement due to plenty of gas remaining, and the working duration per customer, which shows that our system benefits both gas providers and customers.
BibTeX
@misc{yoshida2021long,
  author = {Akihiro Yoshida and Haruki Sato and Shiori Uchiumi and Nariaki Tateiwa and Daisuke Kataoka and Akira Tanaka and Nozomi Hata and Yosuke Yatsushiro and Ayano Ide and Hiroki Ishikura and Shingo Egi and Miyu Fujii and Hiroki Kai and Katsuki Fujisawa},
  title = {{Long-Term Optimal Delivery Planning for Replacing the Liquefied Petroleum Gas Cylinder}},
  year = {2021},
  eprint = {2112.12530},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.12530},
}
Figure