Evaluation of the size of time windows for the travelling salesman problem in delivery operations
- PDF / 1,329,321 Bytes
- 15 Pages / 595.276 x 790.866 pts Page_size
- 44 Downloads / 186 Views
ORIGINAL ARTICLE
Evaluation of the size of time windows for the travelling salesman problem in delivery operations Gerçek Budak1 · Xin Chen2 Received: 18 March 2020 / Accepted: 6 June 2020 © The Author(s) 2020
Abstract A great challenge in operational research is to apply time-efficient algorithms to find the optimal solutions to the travelling salesman problem (TSP) and its many variations. The TSP with time windows (TSPTW) arises due to intense pressure for business to improve customer service. As online shopping becomes more popular, customer satisfaction increases if customers can decide when their orders are delivered to them. Customers may choose a time window, which is defined by an earliest delivery time and a latest delivery time, during which the package is delivered. Delivering packages to multiple customers is a typical TSPTW. One main challenge for a delivery business is to determine the size of the time window (i.e., the difference between the latest and earliest delivery times), which affects delivery cost and customer satisfaction. Although many previous studies investigated the TSPTW, none of those focused on the size of time windows. This study is the first that experiments with different time window sizes and determines their impact on tour duration, customer satisfaction, and solution time of the optimal delivery routes. The experiment results show that increasing the size of the time window decreases tour duration and customer satisfaction and increases solution time. Decreasing the size of the time window increases tour duration and customer satisfaction and decreases solution time. A small solution time is necessary for the scheduling of deliveries to many customers. A large solution time prevents a delivery business from delivering packages using optimal routes, which increases delivery cost and decreases customer satisfaction. The results of this study indicate that a general guideline for business is to allow customers to choose a time window size that is within the cost limit but is sufficiently small to maximize customer satisfaction and optimize delivery routes. Keywords Operational research · Package delivery · Time windows · Travelling salesman problem
Introduction Home delivery business such as DHL [29], FedEx [17], and UPS [33] guarantees delivery to customers on a chosen day. These industry leaders provide a delivery time window of one day. As the competition among home delivery business intensifies, companies compete in two fronts. First, companies try to deliver products to customers as fast as possible. * Xin Chen [email protected] Gerçek Budak [email protected] 1
Department of Industrial Engineering, Ankara Yıldırım Beyazıt University, Ankara, Turkey
Department of Mechanical and Industrial Engineering, Southern Illinois University Edwardsville, Edwardsville, IL 62026‑1805, USA
2
For example, Amazon has been providing two-day deliveries for several years and has recently started one-day deliveries for selected products. This is a dramatic improvement for customer sat
Data Loading...
