A vehicle routing problem of both refrigerated- and general-type vehicles for perishable food products delivery

Journal of Food Engineering 169 (2016) 61e71Contents lists available at ScienceDirectJournal of Food Engineeringjournal homepage: /locate/jfoodengA vehicle routing problem of both refrigerated- and general-typevehicles for perishable food products deliveryByung Duk Song a, Young Dae Ko b, *a Department of Industrial and Systems Engineering, Korea Advanced Institute of Science and Technology, Guseong-dong, Yuseong-gu, Daejeon 305-701,Republic of Koreab Data Analytics Group, Deloitte Consulting, Deloitte Touche Tohmatsu Limited, One IFC, 23, Yoido-dong, Youngdeungpo-gu, Seoul 150-945,Republic of Koreaa r t i c l e i n f oArticle history:Received 15 August 2014Received in revised form30 July 2015Accepted 24 August 2015Available online 28 August 2015Keywords:Perishable food product deliveryRefrigerated-type vehicleMulti-commodityVehicle routing problemHeuristic algorithm1. Introductiona b s t r a c tThis study examines a vehicle routing problem that encompasses both refrigerated- and general-type ofvehicles for multi-commodity perishable food products delivery. It is assumed that both the location andthe volume of the ordered food products for each customer are known. Furthermore, the capacity,maximum delivery time, and available number of both refrigerated- and general-type of vehicles arepredetermined. By reecting these characteristics, we develop a nonlinear mathematical model and aheuristic algorithm to generate efcient vehicle routings with the objective of maximizing the total levelof the customer satisfaction which is dependent on the freshness of delivered food products. In addition,numerical examples and sensitivity analysis are provided to show the validity of the model. The aim ofthis study is to conrm the performance and the availability of refrigerated-type vehicle for perishablefood products delivery compared with general-type one. 2015 Elsevier Ltd. All rights reserved.stores. Customers can get their items within several hours duringthe working day.The development of Information and Communication Technol-ogies (ICT) has dramatically changed peoples daily lives in ourmodern society. Among those changes, peoples shopping style isone of the areas most signicantly affected by those kinds of trends.Before the development of ICT, people would visit local stores topurchase products which they needed in their daily lives. In addi-tion, they tended to visit large warehouse stores usually located farfrom their home to purchase their daily necessities on weekend.People spent a great deal of time for driving toward shoppingstores, choosing various products and carrying out items to theirhome. However, due to the development of ICT, people started topurchase their daily necessities not only at local shopping stores,but also on-line shopping stores through internet or phone. As aresult, market size and market share of on-line shopping hascontinuously increased. As we can see in Fig. 1, the market volumeof online shopping has increased exponentially in Korea.In addition, the perishable food products such as vegetables,shes and dairy goods can be purchased through on-line shopping* Corresponding author.E-mail address: ydkokaist.ac.kr (Y.D. Ko)./10.1016/j.jfoodeng.2015.08.0270260-8774/ 2015 Elsevier Ltd. All rights reserved.The popularization of on-line shopping has allowed people toenjoy the convenience of shopping at their home with little effort.However, at the same time, it causes some troubles for managingthe delivery of food products because of the customer satisfactionissues coming from the freshness of delivered food products. Ingeneral, food products are characterized as perishable items. Theirfreshness is signicantly affected by the time duration and tem-perature environment during the delivery. Thus, when the foodproducts are delivered to lots of customers, it is hard to keep thefreshness of delivered food products due to extended travel timeand frequent stops to serve customers (Hsu et al., 2007). Therefore,the efciency of the vehicle routing scheduling is regarded as animportant issue to maintain the freshness of customers foodproducts. To ensure the freshness of the food products, many onlineshopping stores that sell perishable food products operaterefrigerated-type vehicles that can control their internal tempera-ture using cooling equipment. In this case, customers can get morefresh food products and company can achieve higher level of thecustomer satisfaction. However, refrigerated-type vehicles aremore expensive and require more fuel than general-type vehicles;therefore, it is not easy to operate refrigerated-type vehicles forevery delivery because of the economic issue. As a result, they tend62 B.D. Song, Y.D. Ko / Journal of Food Engineering 169 (2016) 61e71Fig. 1. Increasing the market size of online shopping in Korea.to operate both refrigerated- and general-type vehicles to covercustomer orders.In this research, we consider a vehicle routing problem withboth refrigerated- and general-type vehicles for multi-commodityperishable food products delivery to maximize the total sum ofthe customer satisfaction, which is dependent on the freshness ofthe delivered food products. When vehicles start their travel fromthe depot, the freshness of each food product type is assumed to beperfect. During the delivery, the freshness of each food product isregarded to reduce based on the elapsed traveling time with thefreshness reduction rate of each food product type. However, whenthe food products are delivered via refrigerated-type vehicle,freshness of delivered food is higher due to its freshness-controlfunction. But when the storage door of both general- andrefrigerated-type vehicle is opened for picking out some foodproducts during delivery, all food products which remaining atstorage are regarded to lose certain amount of freshness. In addi-tion, we assumed that the locations, quantity and food product typeof demand (customer orders) and required service for eachcustomer are known and the capacity of each refrigerated- andgeneral-type vehicle can be designed differently. With these con-ditions, we try to derive an efcient delivery schedule for all ve-hicles through mathematical modeling and efcient solvingalgorithm. Based on the result of various numerical experiments,we want to provide a guideline for delivery schedule of multi-commodity perishable food product via refrigerated- and general-type vehicle. Because the purchasing and operating cost of bothrefrigerated- and general-type vehicles are signicantly differentaccording to the specication of them, we do not investigate costrelated elements in this study.2. Literature reviewIn this section, we introduce previous vehicle routing problemsfor perishable food products. If someone wants to investigate anoverall vehicle routing problem, please refer to Eksioglu et al.(2009) for the classication of the vehicle routing problem.Various researches have been conducted to nd an efcientvehicle routing policy and supply chain design for perishable goods.Tarantilis and Kiranoudis (2001) solved a heterogeneous xed-eetvehicle routing problem to nd a vehicle operation schedule forfresh milk. A threshold-acceptance-based algorithm was developedthat aimed to satisfy the needs of a company that planned togenerate a schedule repeatedly, many times over a day. Tarantilisand Kiranoudis (2002) also addressed an open multi-depotvehicle routing problem for distributing fresh meat from depotsto their customers located in an area of the city of Athens. A sto-chastic search meta-heuristic algorithm was proposed to solve theproblem. Prindezis et al. (2003) suggested an application serviceprovider that would offer the services of distribution logistics forcentral food markets that sell and distribute fresh food products. Avehicle routing problem was proposed and solved via appropriatemeta-heuristic techniques. Campbell and Savelsbergh (2005) sug-gested a decision support tool for consumer direct grocery initia-tives. In their article, the authors dened routing and schedulingproblems for grocery delivery service and proposed an insertionheuristic to derive vehicle schedules. In the problem, the companydecides which deliveries to accept or reject as well as vehicleschedules for the accepted deliveries so as to maximize expectedprots. With an unpredictable demand, the authors dene routingand scheduling problems and solving algorithm. Osvald and Stirn(2008) presented an algorithm for the distribution of fresh vege-tables in which the perishability represents a critical factor. Theydealt the problem with time windows and time-dependent travel-times (VRPTWTD) where the travel-times between two nodes arerelated both the distance and on the time of the day. Schmid et al.(2009) developed hybrid solution approach for ready-mixed con-crete delivery. Concrete product is a perishable good, in the sensethat it hardens after a certain amount of time. Due to this charac-teristic, the authors developed an integer mathematical model todeliver concrete products from plants to construction sites using aheterogeneous eet of vehicles. Optimization and heuristic tech-niques are integrated to derive vehicle schedules. Recently, Hasaniet al. (2012) designed a closed-loop supply chain for perishablegoods. In this paper, multiple periods, multiple products and mul-tiple supply chain echelons were considered with uncertain de-mand. Commercial optimization software LINGO version 8 (LINGOsystems Inc.) was applied to derive a solution to the proposedmathematical model. Amorim et al. (2013) considered the issue oflot sizing versus batching in the production and distributionplanning of perishable goods. The authors proved the importanceof lot sizing for make-to-order systems when perishability isexplicitly considered. Govindan et al. (2014) suggested a two-echelon multiple-vehicle location-routing problem for supplychain network of perishable food. A multi-objective optimizationmodel for perishable food supply chain network was developed.The goal was to determine the number and location of facilities andto optimize the amount of products delivered to lower stages androutes at each level. In above researches, heterogeneous types ofvehicles are considered to deliver perishable products. However, norefrigerated type of vehicle was considered to deliver perishableproducts for freshness management.B.D. Song, Y.D. Ko / Journal of Food Engineering 169 (2016) 61e71 63In addition, some researchers addressed the distribution offrozen and chilled food, which is usually called the cold chain.Zhang et al. (2003) presented a tabu search algorithm that opti-mizing the structure of cold chains for the distribution of chilled orfrozen food. Physical distribution systems were structured in such away that the cost of storage and transportation for the whole dis-tribution system was minimized while the product quality re-quirements were fullled. Ying and Ying (2012) proposed anoptimization model that considered the food distribution issuewith a time window for refrigerated food under the condition ofutilizing different modes of transport. Furthermore, the establish-ment of a distribution center was taken into consideration and theobjective function included transportation costs, distribution cen-ter establishment cost, penalty cost, and damage cost. In aboveresearches, authors considered cold chain network design to con-trol freshness issue of delivered products. However, most of themare focused on the network design and specic vehicle routing isnot considered.In this study, we are focusing on the real life issue, which meansmulti-commodity vehicle routing of daily delivery for perishablefood products. To address the freshness issue, we considered theuse of both refrigerated- and general-type vehicles. To the best ofour knowledge, this is a state of the art approach for a heteroge-neous xed-eet vehicle routing problem that considers thesimultaneous operation of both refrigerated- and general-typevehicles to maximize the sum of the customer satisfaction thatcomes from the freshness of each delivery of food products.3. Model development3.1. Problem descriptionpurchase food products by visiting that grocery store, or by usingone of the online channels: Telephone, fax, or internet/mobilewebsite. Even though certain customers purchase food productsdirectly in the store, they can ask for their goods to be delivered.Therefore, this grocery store delivers many perishable food prod-ucts according to the customer orders.It is assumed that the grocery store is located in a metropolitancity. There are several branch stores and each store is assigned atcertain section of the metropolitan city to serve the customer de-mand. Therefore, the delivery distance and duration time of eachcustomer demand is relatively short. In general, this kind of grocerystore tends to cover less than 5 km 5 km area and offer deliveryservices at every 2 or 3 business hours during its business hour. Inaddition, this kind of delivery services tends to be provided as freeof charge for customer conveniences in Korea.To cope with the delivery service requests, the grocery store hasa certain number of both refrigerated- and general-type vehicles,and all food products can be delivered by any type of vehicles. Thedelivery process of this grocery store is as follows: In general, agrocery store collects customer orders over a certain time interval,and then the stores delivery team makes a vehicle routing plan foreach vehicle to deliver the customer orders. However, due to thecapacity limitations, certain customer requests can be denied ordelayed to the next delivery without penalty. Under this situation, agrocery store wants to generate an optimal vehicle routing plan foreach vehicle to maximize the sum of the total customer satisfactionwhich representing the freshness of the delivered food products.Through an optimal vehicle routing plan of each refrigerated- andgeneral-type vehicle, we will evaluate and compare both the per-formance and the availability of them.3.2. NotationsIn this study, we deal with a vehicle routing problem for a localgrocery store that sells perishable food products. The customer cani, j: Index for individual customer nodep: Index for food product type0: Index for indicating depotV: Set of customer nodesV: Set of customer nodes and depot, V0Kr: Set of refrigerated-type vehiclesKg: Set of general-type vehiclesK: Set of all vehicles, KrKgP: Set of food product types.cski,: Customer satisfaction value when customer node i is served by vehicle kCSp,min: Minimum customer satisfaction value for food product type pbrp: Reduction rate of the satisfaction function for food product type p via refrigerated-type vehicle delivery/elapsed timebgp: Reduction rate of the satisfaction function for food product type p via general-type vehicle delivery /elapsed timeopk: Unit satisfaction reduction by storage door opening for vehicle k, food product type pnoi: Number of storage door opening while customer i served by certain vehiclefp(t): Customer satisfaction function for food product type p; it can be differently dened according to the food product nature, but decreased function about elapsed time tfrom a depottij: Traveling time between node i and node jsi: Required service time of customer node iqi: Volume of food products ordered by customer at node iM: Large positive numberckmax: Maximum capacity of vehicle ktkmax: Maximum delivery time of vehicle k at each operationtk0: Preparation time of vehicle k in depotcki : Decision variable on the remaining capacity of vehicle k after serving the customer at node itki : Decision variable on the service start time of customer node i by vehicle kyki : Binary decision variable indicating that customer at node i is served by vehicle kxij: Binary decision variable indicating whether the customer at node j is visited directly after customer of node i is servedxi0j: Binary decision variable indicating whether the customer at node i, depot, and customer at node j are served sequentiallyTDij: Route generation factor; certain vehicle which is located at node i is dispatched at node j which has lowest value of TDij where j2 J and TDij a x Dij qjDij: Euclidean distance between node i and node ja: Conversion parameter between distance and volume for route generation factorXXj2 V; c ktmax;64 B.D. Song, Y.D. Ko / Journal of Food Engineering 169 (2016) 61e713.3. Mathematical model cki qjxij M 1 xij ckj; i; j2 V; c k (20)Based on the addressed problem description, the mathematicalformulations are developed as follows.X XMaximize cskiykik2 K i2 V(1)cski CSp;min$yki;x0i noi; i2 Vi2 V; k2 K; p2 P (21)(22)Subject toXxij 1;i2 Vj2 V (2)xijnoi 1 noj; i; j2 Vnoi is integer; i2 V(23)(24)X xi0j 1; j2 V (3) cki 0; i2 Vk; c k (25)i2 VX xji 1; j2 V (4)tik 0; i2 V; c k (26)i2 VXi2 VXxj0ixij 1;Xj2 Vxji; j2 V(5)(6)yki2 f0; 1g;xij2 f0; 1g;xi0j2 f0; 1g;i2 V; c ki; j2 Vi; j2 V(27)(28)(29)i2 V i2 VXi2 Vx0i Xi2 Vxi0 (7)3.3.1. Objective functionThe objective function stands for the total sum of the customerxi0 xoj 2$xi0j (8) satisfaction. The customer satisfaction value cski is dened as inEquation (30).Kyki 1; i2 V (9) cski; Max fp tikj2 Vtjk t0j x0j$ykj sik1Kykiykj xij; i; j2 V (10)okp$noi;i2 V; k2 K; p2 P(30)Note that customer satisfaction function, fp(t), is decreasingfunction according to the elapsed time from a depot to certaink1X Xx0iyki xi0yki;i2 V i2 Vh iMin t0i$x0i$yki t0ki2 Vh iMax tik si ti0xi0i2 Vc ktjk; j2 V; c kk(11)(12)(13)customer node when that customer orders food product type p.The customer satisfaction value is regarded as decreasing func-tion according to the elapsed time from a depot. In detail, if boththe customer node i and j are served at same route, the elapsedtime of customer node i can be expressed Mintki tkj t0j si,which is a