Development of Analytical Solution Methodologies for a Class of Problems in Last Mile Delivery (LMD) of LPG Cylinders (LPG-C) in India

Abstract

Last Mile Delivery (LMD) relates to all the logistics related activities carried out towards delivery of shipments to the end customers and is considered as the most expensive and time-consuming stage in the supply chain management. Today, almost every service sector industry such as e-commerce, online food delivery, courier delivery, etc., render LMD as a service to the customers. In India, among various LMD businesses, distribution of Liquified Petroleum Gas cylinders (LPG-C) is one of the prominent one. LPG is widely used as cooking fuel and has many industrial applications. In India, it is protected under the essential commodities act, whose supply, if disrupted, will disturb everyday public life. LPG-C are bottled and distributed by both public and private oil marketing companies or petroleum companies. The LMD of the bottled LPG-C is done by many distributors, selected by each of the petroleum companies. For avoiding hazardous accidents and damage to the society due to the movement of LPG-C from petroleum companies to the distributors and from distributors to the end customers, the petroleum companies along with the Government of India, have constituted the Marketing Discipline Guidelines which define delivery policies, targeted delivery time, cylinder handling procedures and practices, and various penalties and actions taken against erring distributors. Though the delivery guidelines and targeted delivery time are constituted, it is to be noted that there is “no standard operating procedure” provided for the distributors by the petroleum company. However, the general delivery operation processes carried out by majority of the distributors in LMD of LPG-C (LMD-LPG-C) are learned based on the knowledge input provided by three large scale LPG-C distributors and their delivery agents in the metro city: Chennai. The challenges / issues faced by the distributors, particularly w.r.t delivering the LMD-LPG-C within the targeted delivery time of 24 hours lead time or same day delivery and prevention of black-market deviation are considered in this study. Considering the operations related challenges / issued faced by the distributors, in this study, the following three decision problems related to LMD-LPG-C are considered: Daily delivery sequence to deliver LPG-C to the end customers is by-and-large, based on non-rational rudimentary approaches / experience and is done by each of the delivery agents. This increases the overall distance travelled by the delivery agents in LMD-LPG-C. Accordingly, the determination of optimal or efficient daily delivery sequence is considered as the first decision problem of this study. Each of the delivery agents make multiple trips between the delivery area assigned to him and the office location for restocking filled LPG-C with respect to his delivery-vehicle capacity and the number of targeted LPG-C given to him for his day-delivery. The multiple trips make significant contribution to the overall distance travelled by each of the delivery agents in LMD-LPG-C. Minimizing this restocking distance is addressed as second decision problem in this study. At the time of delivering the LPG-C at the customer locations, each of the customers attest/sign the order bill copy of LPG-C ordered by the customer for delivery authentication / confirmation in India. According to the distributors, this naïve practice of authenticating led to an increase in cases of black-market deviation, delivery delay complaints and inventory accounting problems for the distributors. Developing a proven system for minimizing these issues is addressed as the third decision problem in this study. From the analysis of the closely relate literature, to the best of our knowledge, it is observed that there is no earlier studies contributed solution methodologies for each of the decision problems of LMD-LPG-C considered in this study. With this premise, in this study optimal or efficient solution methodology is proposed for each of the three decision problems. Further, a summary on the research processes carried out to determine the optimal or efficient solution methodology for each of the decision problems are presented as follows: The decision problem on determining optimal or efficient delivery sequencing (DS) decision in LMD-LPG-C is approached as Multiple Traveling Salesman Problem (MTSP) considering the multiple trips made by the delivery agents due to the limited cylinder carrying capacity of their delivery vehicles. For optimal DS decision, a suitable (0-1) Integer Linear Programming (ILP) model is developed. The workability of the proposed (0-1) ILP is tested through a numerical example, representing the DS decision problem of a delivery agents. Due to computational intractability in getting optimal DS decision using exact method, alternate non-conventional optimization algorithm: Meta-Heuristic Algorithms (MHA): Tabu Search Algorithm (TSA), Simulated Annealing Algorithm (SAA), Genetic Algorithm (GA) and Ant Colony Optimization (ACO) are considered for determining efficient DS decision of LMD-LPG-C problem. The MHA: TSA and SAA are referred to as single solution algorithm and GA and ACO as population search algorithm. In case of the MHA, the initial solution(s) and MHA-parameter values significantly influences the performance of the MHA in obtaining the (near) optimal solution. Consequently, before understanding the performance of each of the MHA considered in this study, the initial solution(s) and best fit MHA-parameter values for each of the MHA considered is determined using the given set of orders delivered by a delivery agent in a day. Particularly, for single solution-based MHA-algorithms, three methods: random method, nearest neighbour method, and the DS decision by the delivery agents for the given set of customer orders are used for obtaining initial solution. Further. the best method for obtaining the initial solution is identified as a part of the parameter tuning process. For population search algorithms the required initial solutions are obtained using the random method for the given set of orders considered for a delivery agent. The number of initial solutions for the population search algorithms is determined as a part of the parameter tuning process [that is for GA the number of initial solutions is controlled by the parameter “Population Size” and for ACO it is controlled by the “Number of Ants” parameter]. For each of the MHA: SAA, GA and ACO, the MHA-parameter tuning is done by following the Taguchi Orthogonal Array (TOA) technique. Whereas the complete enumeration technique is used in case of the MHA: TSA since only one parameter: the number of iterations need tunning in TSA. For single solution-based MHA: TSA and SAA, the total travel distance for the solution obtained for each of the initial solutions and for each of the MHA-parameter(s) value is computed. The combination of initial solution and MHA-parameter values that result in DS solution with the least total travel distance is determined. Now the MHA-parameter values that resulted the least total distance is considered to be the best fit parameter value for the respective MHA. In case of population search algorithm, the combination of MHA-parameter values that result in DS solution with the least total travel distance is determined and the corresponding MHA-parameter values is considered to be the best fit parameter values for the respective MHA. For understanding the performance evaluation of the selected MHA, real-life data from the case study organization is collected. Particularly, the data on (a) 216 set of lists of customer-orders delivered in the month of February 2024 by each of the 8 delivery agents (DA), and (b) the actual DS decision of each of the DA for each of the 216 set of lists of customer-orders delivered in the month of February 2024 of the case study organization are collected and are considered as test data. For each of the data on 216 DS decision by DA (DS-DA), the total distance travelled is computed by generating the required inter distance matrix considering each of the 216 DS decision. This computed total distance, corresponding to each of the 216 DS-DA is considered as benchmark solution. Further, for each of the 216 set of lists of customer-orders delivered data and the respective inter-distance matrix considering each of the 216 set of lists of customer-orders delivered are given as input to each of the selected MHA and obtained (a) 216 DS decision for each of the selected MHA, and (b) total travel distance corresponding to each of the 216 DS decision obtained from each of the selected MHA. Now the benchmark solution (total distance) w.r.t the existing data on the 216 DS-DA for the month of February 2024 is compared empirically and statistically with the total distance yielded by each of the selected MHA for the same 216 set of lists of customer-orders delivered. From the performance analyses, it is observed that the DS solution by TSA (DS-TSA) is giving on an average better DS decision. The second decision problem on minimizing the distance travelled by the delivery agents for restocking in LMD-LPG-C is addressed by recommending Dynamic Temporary Re-Stocking Location (DTRSL) to station the mini-trucks, which are used to transport LPG-C between the warehouse and office location in the current practice and for the delivery agents to collect / re-stock with filled LPG-C for their routine delivery to customers. An algorithm is developed to determine the proposed DTRSL, considering the cluster of customers who are expected to place orders in the study period (i.e. in a month) – referred to as Customer-cluster – and the number of mini trucks operated by the distributor. Five major integrated decisions are involved in determining the DTRSL and they are (i) Number of Days between the Customer-Last Order and the Expected New Order (ND-CLO-ENO) for the entire customers, (ii) Expected Order Date Range (EODR) for the entire customers, (iii) Segregated-customers for the study period of one month (February 2024), (iv) Clustered-customers for each of the 3 planning period (each planning period comprised of 10 days) of the study period considering the number of mini trucks used for moving filled LPG-C from warehouse to the proposed DTRSL, and (v) DTRSL for each of the Clustered-customers. To obtain the Clustered-customers and determine the DTRSL, all the customer’s order booking dates received from January 2018 to February 2024 is collected which accounts for 550690 datapoints. This collected data has the details on the customers unique consumer number and their order booking dates. From the collected data, customer-wise the multiple ordering dates (MOD) received between January 2018 to February 2024 are segregated, which accounts for 10206 unique customer’s MOD data. Using the 10206 customer’s MOD data, customer-wise Number of Days between every Successive Order (ND-SO) is computed and represented as a time-series data. The number of datapoints in each of the ND-SO data varies between 0 to 73 and each of the ND-SO data represents the customer’s unique ordering pattern. Further customers who are dormant [that is customers who have not placed any orders in the last two years] and customers with less than 6 datapoints in their ND-SO data are not considered to determine DTRSL and this further reduces the ND-SO data to 9014. This ND-SO data is used to determine the customer-wise Number of Days between Customer-Last Order and Expected New Order (ND-CLO-ENO) using Machine Learning based forecasting methods. The last datapoint in each of the ND-SO data is the value the forecasting methods are intended to predict. The forecasting methods considered are trained and its performance are evaluated using the training and testing dataset respectively and are obtained from the 9014 customer’s ND-SO data. The last 6 datapoints from each of the ND-SO data are obtained and stored as testing dataset which accounts for 9014 time series data and each of these has with 6 datapoints. To obtain the training dataset, only customers with more than 6 datapoints in their ND-SO data are considered which reduces the number of customers to 8953 from 9014. To ensure the forecasting methods are not exposed to the datapoint which it is supposed to predict, in all the 8953 customer’s ND-SO data the last datapoint is ignored and are subjected to data subsampling using sliding window technique. This data subsampling process ensures the availability of adequate data of consistent dimensions to train the considered forecasting methods. Accordingly, from the 8953 customer’s ND-SO datapoint, 296394 time series data with 6 datapoints each is obtained and is considered as training dataset. Finally, the outliers in each of the time series data in both training and testing dataset are identified using Tuckey’s Inter Quartile Range method and are replaced by the mean value of the remaining non-outlier datapoints in each of the time series data. The forecasting methods are trained on the training dataset, and its performance is evaluated using the testing dataset with r^2 score and Mean Absolute Error (MAE) as evaluation metrics. The selected forecasting method’s performance is evaluated on its default parameter values and then they are subjected to parameter tuning for better performance using Grid Search CV technique. From the computational analysis Random Forest Regression is identified as the best performing among the forecasting methods considered and for each of the 9014 customers (testing dataset) the ND-CLO-ENO is predicted using the trained Random Forest Regression forecasting model. Using a simple mathematical equation, considering (i) the predicted ND-CLO-ENO data, (ii) each of the customers previous order booking date, and (iii) the MAE of the trained Random Forest Regression forecasting model, the Expected Order Date Range (EODR) for each of the 9014 customers are determined. The location details (geographic coordinates) for each of the 9014 customers are obtained from the study organization and all the customers whose EODR either partially or completely falling within the study period (February 2024) are obtained and are referred to as Segregated-customers. The location details of the Segregated-customers are provided as input to the K-Means clustering algorithm and planning period-wise (roughly ten days per planning period) the data on Clustered-customers are obtained. Using the centroid function of the K-Means clustering algorithm, the centroid for each of the Clustered-customers are determined and is prescribed as DTRSL. Finally, the performance of the DTRSL is determined considering the efficient DS method (that is TSA) obtained as an outcome of decision problem 1 and actual customers order received during the study period, which accounts for 4720 actual customer orders. The required inter-distance matrix for each of the 4720 customer’s delivery location and office location is computed using Euclidean distance formula. Similarly, inter-distance matrices for the DTRSL and each of the customers who placed order during each of the 3 planning periods having 10 days for each of the 3-planning period of a month from the 4720 actual customer orders are computed [that is, 3 inter-distance matrices are computed]. The orders in each of the clusters (referred to as order corpus) are sequenced using Nearest Neighbour algorithm and the sequenced order corpus are sub-sampled into multiple order subsets each with a maximum of 30 orders in it. Accordingly, a total of 199 order subsets are obtained from the 4720 orders received during the study period and these are considered as test data. DS solution with office as restocking location is obtained using the DS method: TSA and the total travel distance for each of the 199 order subsets are computed and considered as benchmark solution. Further, the DS solution for each of the 199 order subsets is obtained with DTRSL as re-stocking location and the total travel distance is computed. The net savings computed with DTRSL as re-stocking location indicated that the total distance travelled by the delivery agent is significantly minimized. The final decision problem concerning the lack of a delivery authentication system in LMD-LPG-C is addressed by proposing a Prototype Delivery Authentication System (P-DAS). The proposed P-DAS is developed with an Image Classification Module (ICM) and an Image Metadata Extraction and Verification Module (IMEVM). The image dataset of LPG-C (both steel and composite type available in market) and other similar looking objects like water-can, cool drinks can and fire extinguishers are collected and are used to train the ICM developed with MobileNet architecture. The images are collected from open source (internet) and are captured using smart phone cameras in various environmental backgrounds. A total of 200 images with 50 images under each category [combined 50 images of both the types of LPG-C in one category] are collected. The collected image data are subjected to a series of data preparation and pre-processing steps to improve the training efficiency of the ICM. Training techniques like data augmentation, transfer learning and Computer Unified Device Architecture computing are used to train the ICM efficiently. The performance of the ICM is evaluated using evaluation metrics like accuracy and f1-score. The evaluation results demonstrate the ICM's ability to clearly differentiate between LPG-C images and other similar-looking objects. The IMEVM is a structured logic which is developed to extract the metadata from the input image and verifies if the image is captured at the customer’s delivery location or not. The metadata are extracted using the EXIF library and the distance between the place of the image capture and customer’s actual delivery location which is computed using the Euclidean distance formula. If the distance computed is less than 10 meters (an arbitrary threshold), the IMEVM will authenticate the delivery and record the date and time of delivery. If any of the two stage verification processes [that is if the image not recognised as LPG-C by the ICM or distance between the place of image capture and customer’s actual delivery location is greater than 10 meters] fails, the P-DAS does not authenticate the delivery. Finally, the performance of the P-DAS is evaluated using a set of real-time data obtained from the case study organization. The performance analysis highlights the adaptability of the P-DAS in LMD-LPG-C and its potential to assist distributors in delivering LPG-C to the correct customers. The managerial implications and the proposed solution methodologies for each of the 3 decision problems for implementing the research outcomes in real-time are discussed based on the contributions from these problems. Furthermore, a standard operating procedure is proposed to ensure all the benefits of adopting and implementing the proposed solution methodologies for each of the three decision problems considered in the study. While this study aims to address the real-time problem in LMD-LPG-C, certain limitations remain. These include (a) only on domestic cylinder demand and not commercial cylinder demand, (b) the inability to dynamically insert new orders into the existing delivery sequence as replacements for orders where customers are unavailable at the time of delivery, (c) not considering restricted locations such as hospitals and schools when recommending the DTRSL, and (d) not studying the impact of dynamic real-time events such as order cancellations. In addition to overcoming the limitations mentioned in the study, there are certain immediate future research directions for the problem studied in this thesis such as, development of decision support system incorporating the proposed solution methodologies for ease of utilization by every distributors, ergonomic analysis of fatigue level of the delivery agents, approaching the study from sustainability perspective, and the role and adaptation of IoT and Industry 4.0 to forecast customers next order date based on their consumption.