Transcription
Proceedings of the 11th Annual International Conference on Industrial Engineering and Operations ManagementSingapore, March 7-11, 2021Application of Vehicle Routing Problem to DetermineOptimal Route in Fuel Distribution: A Case StudyEra Febriana AqidawatiMaster Program of Industrial Engineering Department, Faculty of EngineeringUniversitas Sebelas MaretSurakarta, lana Ichwan Anshory, Aprilia Dityarini, Yuniaristanto, Wahyudi Sutopo, BrahmastyaArtantoIndustrial Engineering Department, Faculty of EngineeringUniversitas Sebelas MaretSurakarta, [email protected], [email protected], .ac.id, [email protected] a country with quite a lot of motorized vehicle users, fuel is an important requirement for the Indonesian people.Apart from being used for transportation, fuel is also used to support various sectors. Thus, the supply of fuel issomething that is vital to pay attention to, especially in relation to fuel distribution. Problems related to thedistribution of fuel include making decisions regarding the distribution routes between gas stations. The choice ofvehicle route will determine the total distance traveled by the fleet to create an optimal distribution system, so thatroute selection must be effective and efficient. This study discusses the distribution of fuel from Boyolali FuelTerminal to gas stations in several of the residences in Surakarta and western eastern Java. Vehicle Routing Problem(VRP) is used to solve the problem and Google OR-Tools Algorithm and Python programming are used to get theminimum total distance from the fuel transport truck. The results of this study are the acquisition of a newdistribution route so that the distance of transportation decreases by about 60% than before.KeywordsFuel, distribution route, vehicle routing problem1. IntroductionA company must be able to optimize its distribution system in order to compete with other similar companies. Oneway is by optimizing transportation. One of the problems in transportation is Vehicle Routing Problems (VRP),which are designing a set of low-cost vehicle routes where each vehicle starts and ends at the depot, each consumeris only served once by a vehicle, and the total demand carried does not exceed the vehicle's capacity. Thistransportation contributes 1/3 to 2/3 of the total distribution cost (Toth, 2002). VRP is a problem of optimization,which relies on determining the shortest transport routes for a strictly limited number of means of transport, whoseaim is to handle a set of customers located in different geographic locations while maintaining defined restrictions(Bruniecki, 2016).The Boyolali Fuel Terminal is assigned with distributing fuel oil to refueling stations in several areas, such as SouthSemarang, Salatiga, Surakarta, Sragen, Boyolali, Sukoharjo Klaten, Wonogiri, Karanganyar, Purwodadi, Blora,Ngawi, Magetan and Pacitan. Boyolali Fuel Terminal distributes BBM to 238 gas stations, industry, PT KAI, PTPLN, and the TNI / POLRI. The distribution pattern of Boyolali Fuel Terminal uses a zoning system. The zoningsystem is based on the distance of the gas station to the Boyolali Fuel Terminal. The zoning system is divided into IEOM Society International2129
Proceedings of the 11th Annual International Conference on Industrial Engineering and Operations ManagementSingapore, March 7-11, 2021three, namely a distance of less than 30 km, a distance between 30 km to 60 km and a distance of more than 60 km.According to Pertamina, the zoning system is not yet optimal so that a more optimal distribution system is needed.The development of the community's economy makes the expansion of development in various fields, so that thefuel distribution system becomes more complex. In a distribution system, one important factor to consider is theroute chosen. The route chosen is the most important element in determining the distance to be traveled and thecosts to be incurred. If the selected route is optimal, the distribution system will become more effective and efficient.The optimal route can minimize transportation costs incurred.There are many variants of VRP study, depend on the condition of the company. Previous research that have beendone by Sharma et al. (2018) stated that there is 14 variants of VRP, there are Capacitated Vehicle Routing Problem,Multiple Depot Vehicle Routing Problem, Periodic VRP, Split Delivery VRP, VRP With Satellite Facilities,Heterogeneous Fleet VRP, VRP with time windows, Green VRP, Generalised VRP, Stochastic VRP, Rich VRP,Open VRP, VRP with Pick-Up and Delivery, Asymmetric VRP. VRP problems can be solved with differentalgorithms, such as this previous research in Table 1.Table 1. Previous Research of VRP with different algorithmsNo.1AuthorsSkok, et.al (2000)AlgorithmsGenetic Algorithms2Surjandari, et.al (2011)Tabu Search3Benantar and Ouafi(2012)Tabu Search4Battarra, et.al (2014)Branch and Cut and Branch and Cut andPrice5Reed, et.al (2014)Ant Colony6Marc, et.al (2015)Genetic Algorithms (GA) and SimulatedAnnealing (SA)7Vidal, et.al (2015)Iterated Local Search Algorithm danHybrid Genetic Search8Henke, et.al (2015)Neighborhood Search9Izquierdo, et.al (2016)Record to record travel10Yahyaoui, et.al (2018)Neighborhood Search and GeneticAlgorithmsVRP ProblemCapacitated VRP with Heuristic methodMulti Compartment, Capacitated, TimeWindow, and Loading Unloading VRPwith Heuristic methodMulti Compartment and Time WindowVRP with Heuristic methodCluster and Capacitated VRP withcombination of Heuristic and ExactApproachMulti Compartment, Clustered,Capacitated, Loading Unloading VRP withMetaheuristic methodCapacitated and Clustered VRP withHybrid Use (Metaheuristic and Heuristicmethod)Capacitated and Clustered VRP withHybrid Use (Metaheuristic and Heuristicmethod)Multi Compartment and Capacitated VRPwith Heuristic methodCapacitated and Clustered VRP withMetaheuristic methodMulti Compartment, Clustered, andCapacitated VRP with MetaheuristicmethodIn this paper, we are interested by VRP with multi capacity of vechicles and stations. In VRP, if each vehicle isassigned a certain load capacity, then this problem is known as Capacitated VRP (Toth and Vigo, 2002). Thisresearch will optimize the distribution route of the TBBM Boyolali oil truck to all its refueling stations. Each oiltruck used has a different capacity. Refueling stations also have individual demands. Therefore, the type of VRP thatis suitable for use is CVRP. If researchers have already tried research VRPs with modeling and algorithmicapproaches, practical implementation and employs programming techniques is this paper focus. We use Google ORTools in data processing, an optimization tool developed by Google with its own algorithm. In implementing GoogleOR-Tools we use Python programming language. IEOM Society International2130
Proceedings of the 11th Annual International Conference on Industrial Engineering and Operations ManagementSingapore, March 7-11, 20212. Quantitative ApproachVehicle Routing Problem (VRP) is one of the combinatorial optimization problems that has many applications in theindustrial field (Geetha, 2016). VRP has several main types of problems namely Capacitated Vehicle RoutingProblems (CVRP), Vehicle Routing Problems with Pick Up and Delivery (VRPPD), Distance Constrained VehicleRouting Problems (DCVRP), Vehicle Routing Problems with Multiple Depots (VRVP) VRPMD), Split DeliveryVehicle Routing Problem (SDVRP), and Vehicle Routing Problem with Time Windows (VRPTW) (Toth and Vigo,2002). In this case the customer's request is limited by the amount of load possessed by the capacity of the Tanker,so the Capacitated Vehicle Routing Problem (CVRP) is used which is an optimization problem to determine theroute with minimal cost.Boyolali Fuel Terminal has 14 areas covered as a distribution network which the total number of fuel stations as ofDecember 2018 is 238 stations. Meanwhile, the total demand is around 8168 kiloliters per month. The Demand perArea shown in Table 2 below.Table 2. Demand per Area for Boyolali Fuel TerminalAreaQuantityAverage Demand in Kl (Jan-Nov 2018)Sourthen 7Magetan16272Pacitan9436In meeting the demand at 238 fuel stations that are spread out, TBBM has a large fuel tank fleet of 103 trucksoriginating from outsourcing. The trucks are not only available in one capacity, but three. The trucks are available incapacities of 16, 24 and 32 kiloliters. The Capacity of Truck shown in Table 3 below.Table 3. The Capacity of Total TruckCapacityQuantityTruck A1629Truck B2453Truck C3221In this study, the distribution of fuel from Boyolali TBBM will only be seen in distribution to the Boyolali gasstation. The total number of Boyolali gas stations was 16 coded 44,573.01 to 44,573.16. The distance from TBBMand each gas station can be seen in the Table 4. Demand for each gas station can also be seen in the picture. In thisstudy, the demand is assumed that for one month there will be 80 shipments to each gas station. IEOM Society International2131
Proceedings of the 11th Annual International Conference on Industrial Engineering and Operations ManagementSingapore, March 7-11, 2021Table 4. Distance Between Each Gas Stations and its DemandFrom/To 16DemandTBBM 44.573.01 44.573.02 44.573.03 44.573.04 44.573.05 44.573.06 44.573.07 44.573.08 44.573.09 44.573.10 44.573.11 44.573.12 44.573.13 44.573.14 44.573.15 0671112574In addition, the number of trucks operating that deliver fuel to the Boyolali gas station is assumed to be 12. Thetruck consists of two variations of capacity, 16 kiloliters and 32 kiloliters. Trucks with a capacity of 16 kiloliterstotaled 10 units while trucks with a capacity of 32 kiloliters totaled 2 units.3. Results and discussionData processing is done using OR-Tools software. OR-Tools is an open source optimization software developed byGoogle AI, created to solve the world's toughest problems in vehicle routing, flow, integer and linear programming,and obstacle programming (Google, 2020). After modeling the problem in the user's choice programming language,the user can use one of many problem-solving examples to solve: commercial problem solving such as Gurobi orCPLEX, or solving open-source problems such as SCIP, GLPK, or Google GLOP and CP award-winning problems–SAT.In this paper, there are two stages. The first stage is the process of making programming logic in Python using theGoogle OR-Tools algorithm. The second stage is the process of running data to finally get the optimal number ofroutes. The first step is to enter the distance data between nodes, namely the distance between Boyolali TBBM toeach gas station in Boyolali and the distance between each gas station in Boyolali itself. This distance data is enteredinto a matrix format as shown in Figure 1. After entering distance data, the next step is to enter demand data per gasstation, the number of vehicles and the capacity of each vehicle. They are shown in Figure 2. The last step is to runpython software. At this stage python will do several iterations. The trial uses the heuristic method, where thismethod will find the optimal solution by looking directly for the value obtained in each iteration. The results of therunning are as follows illustrated in Figure 3.Figure 1. Data Distance Matrix Input on Python IEOM Society International2132
Proceedings of the 11th Annual International Conference on Industrial Engineering and Operations ManagementSingapore, March 7-11, 2021Figure 2. Data Demand, Vehicle Capacities and Number Matrix Input on PythonFigure 3. Route for Each Vehicle on PythonFrom the results of simulation by Python, several routes are generated. Of the total 12 trucks there are 8 trucksoperating and there are 4 trucks that are not operating. Trucks number 1, 2, 3 and 4 with a total capacity of 16kiloliters do not deliver. Figure 4 illustrates the solution for the fuel distribution route.The route for truck number 5 with a total capacity of 16 kiloliters is to deliver gas stations 44.573.13 for 12 kilolitersand to 44.573.16 for 4 kiloliters. The total distance traveled by this route is 24 km and the total fuel transported is 16kiloliters. The route for truck number 6 with a total capacity of 16 kiloliters is only to deliver to gas station44.573.01 for 15 kiloliters. The total distance traveled by this route is 60 km and the total fuel transported is 15kiloliters. The route for truck number 7 with a total capacity of 16 kiloliters is only delivering to gas stations44.573.04 for 7 kiloliters. The total distance traveled by this route is 10 km and the total fuel transported is 7kiloliters.The route for truck number 8 with a total capacity of 16 kiloliters only delivers 44,573.06 gas stations as many as 12kiloliters. The total distance traveled by this route is 62 km and the total fuel transported is 12 kiloliters. The routefor truck number 9 with a total capacity of 16 kiloliters delivers 7 kiloliters of gas stations as many as 7 kilolitersand 5 kiloliters to 44.573.14. The total distance traveled by this route is 68 km and the total fuel transported is 12kiloliters. The route for truck number 10 with a total capacity of 16 kiloliters is delivering to gas station 44.573.08with 6 kiloliters and to 44.573.11 with 7 kiloliters. The total distance traveled by this route is 35 km and the totalfuel transported is 13 kiloliters. The route for truck number 11 with a total capacity of 32 kiloliters is to deliver togas station 44.573.02 for 10 kiloliters, to 44.573.03 for 11 kiloliters, to 44.573.12 for 11 kiloliters. The total distancetraveled by this route is 37 km and the total fuel carried is 32 kiloliters. The route for truck number 12 with a totalcapacity of 32 kiloliters delivers 6 kiloliters to gas stations 44 kiloliters, to 44.573.05 as many as 7 kiloliters, to44.573.09 as many as 10 kiloliters, and to 44.573.15 as many as 7 kiloliters. The total distance traveled by this routeis 36 km and the total fuel transported is 30 kiloliters. IEOM Society International2133
Proceedings of the 11th Annual International Conference on Industrial Engineering and Operations ManagementSingapore, March 7-11, 2021GS 6GS 18GS 312 kl11 klGS 715 klGS 211 klGS 12117 klGS 97 klGS 13124 klGS 1697 klGS 555 klGS 1510 klGS 10610 kl6 kl12 klGS 4GS 11107 kl77 klFuelterminal6 klGS 14GS 8Figure 4. Fuel distribution route solutionThe total distance traveled by trucks on all routes is 332 km, while the total fuel carried is 137 kiloliters. The totalfuel has been able to meet all the demands that exist at each gas station in Boyolali. There are 4 trucks that areunemployed, these trucks can be allocated to gas stations outside Boyolali so that they can operate more effectivelyand efficiently.4. ConclusionThe Boyolali Fuel Terminal is tasked with distributing fuel oil to refueling stations in several areas, such as SouthSemarang, Salatiga, Surakarta, Sragen, Boyolali, Sukoharjo Klaten, Wonogiri, Karanganyar, Purwodadi, Blora,Ngawi, Magetan and Pacitan. Boyolali Fuel Terminal distributes BBM to 238 gas stations. It has to optimize thedistribution of fuel to gas stations to achieve operational excellence. In this study suggest Boyolali Fuel Terminal touse only 8 trucks to distribute fuel in Boyolali area. Another trucks can be rellocated to another area. This article hascertain limitation that should be overcome in order to provide in deep analysis on the vehicle distribution analysis.For further research will complete the research with additional constraints such as time windows, pickup anddeliveries, dimensions and resource constraints to increase the closeness of the solution to the real system.ReferencesBattara, M., Edorgan, G., and Vigo, D., Exact Algorithms for the Clustered Vehicle Routing Problem, OperationsResearch, vol. 62, no. 1, pp. 58-71, 2014.Benantar, A., and Ouafi, R., Optimization Of Vehicle Routes: An Application To Logistic And Transport Of TheFuel Distribution, 9th International Conference on Modeling, Optimization & SIMulation, Bordeaux, France,June 6-8, 2012. IEOM Society International2134
Proceedings of the 11th Annual International Conference on Industrial Engineering and Operations ManagementSingapore, March 7-11, 2021Bruniecki, K., Chybicki, A., Moszynski, M., & Bonecki, M., Evaluation of vehicle routing problem algorithms fortransport logistics using dedicated GIS system, Baltic Geodetic Congress (BGC Geomatics), Gdansk, Poland,June 2-4, 2016, pp. 116-121, 2016.Cetin, S., A heuristic algorithm for vehicle routing problems with simultaneous pick-up and delivery and hard timewindows, Open Journal of Social Sciences, vol. 3, no. 03, p. 35, 2015.Expósito-Izquierdo, C., Rossi, A., and Sevaux, M., A two-level solution approach to solve the clustered capacitatedvehicle routing problem, Computers & Industrial Engineering, vol. 91, pp. 274-289, 2016.Geetha, S., Poonthalir, G., and Vanathi, P., Metaheuristic approach for the multi-depot vehicle routing problem,Applied Artificial Intelligence, vol. 26, no. 9, pp. 878-901, 2012.Google, About OR-Tools, Available: ction/overview, May 21,2020.Henke, T., Speranza, M. G., and Wäscher, G., The multi-compartment vehicle routing problem with flexiblecompartment sizes, European Journal of Operational Research, vol. 246, no. 3, pp. 730-743, 2015.Marc, A. H., Fuksz, L., Pop, P. C., and Dănciulescu, D., A novel hybrid algorithm for solving the clustered vehiclerouting problem, International Conference on Hybrid Artificial Intelligence Systems, pp. 679-689, 2015.Reed, M., Yiannakou, A., and Evering, R., An ant colony algorithm for the multi-compartment vehicle routingproblem, Applied Soft Computing, vol. 15, pp. 169-176, 2014.Sharma, S. K., Routroy, S., and Yadav, U., Vehicle routing problem: recent literature review of itsvariants, International Journal of Operational Research, vol. 33, no. 1, pp. 1-31, 2018.Skok, M., Skrlec, D., and Krajcar, S., The genetic algorithm method for multiple depot capacitated vehicle routingproblem solving, KES'2000. Fourth International Conference on Knowledge-Based Intelligent EngineeringSystems and Allied Technologies. Proceedings (Cat. No.00TH8516), Brighton, UK, 30 Aug.-1 Sept. 2000, vol.2, pp. 520-526, 2000.Surjandari, I., Rachman, A., Dianawati, F., and Wibowo, R. P., Petrol delivery assignment with multi-product,multi-depot, split deliveries and time windows, International Journal of Modeling and Optimization, vol. 1, no.5, p. 375, 2011.Vidal, T., Battarra, M., Subramanian, A., and Erdogˇan, G., Hybrid metaheuristics for the clustered vehicle routingproblem, Computers & Operations Research, vol. 58, pp. 87-99, 2015.Yahyaoui, H., Kaabachi, I., Krichen, S., and Dekdouk, A., Two metaheuristic approaches for solving the multicompartment vehicle routing problem, Operational Research, pp. 1-24, 2018.BiographiesEra Febriana Aqidawati is a student at Master Program of Industrial Engineering Department, Universitas SebelasMaret, Surakarta, Indonesia. She is also a research assistant in the Laboratory of Logistics System and Business inthe Department of Industrial Engineering, Faculty of Engineering, Universitas Sebelas Maret. She obtained herBachelor of Engineering degree in Industrial Engineering from Universitas Sebelas Maret in 2018. Her researchinterests are techno-economics, logistics and supply chain management, operation research, and business strategicmanagement. She has published 10 articles, 6 of them are Scopus indexed.Maulana Ichwan Anshory is an undergraduate student of Industrial Engineering Department of UniversitasSebelas Maret, Surakarta, Indonesia. He is also a research assistant at Industrial System Design and OptimizationLaboratory in Industrial Engineering Department. His research interests are enterprise information system, decisionsupport system and data science.Aprilia Dityarini is an undergraduate student of Industrial Engineering Department of Universitas Sebelas Maret,Surakarta, Indonesia. She is also a research assistant at Quality System Laboratory in Industrial EngineeringDepartment. Her research interests are quality sytem, quality management and production oprimization.Yuniaristanto is a lecturer and researcher in Departement of Industrial Engineering, Universitas Sebelas Maret. Hisresearch interests are supply chain, simulation modeling, performance measurement and technologycommercialization. He has publications that indexed by Scopus, 41 articles with 4 H-index. His email [email protected]. IEOM Society International2135
Proceedings of the 11th Annual International Conference on Industrial Engineering and Operations ManagementSingapore, March 7-11, 2021Wahyudi Sutopo is a professor in industrial engineering and coordinator for the research group of industrialengineering and techno-economy (RG-RITE) of Faculty Engineering, Universitas Sebelas Maret (UNS), Indonesia.He earned his Ph.D. in Industrial Engineering and Management from Institut Teknologi Bandung in 2011. He hasdone projects with Indonesia endowment fund for education (LPDP), sustainable higher education research alliances(SHERA), MIT-Indonesia research alliance (MIRA), PT Pertamina (Persero), PT Toyota Motor ManufacturingIndonesia, and various other companies. He has published more than 130 articles indexed Scopus, and his researchinterests include logistics and supply chain management, engineering economy, cost analysis and estimation, andtechnology commercialization. He is a member of the board of industrial engineering chapter - the institute ofIndonesian engineers (BKTI-PII), Indonesian Supply Chain and Logistics Institute (ISLI), Society of IndustrialEngineering, and Operations Management (IEOM), and Institute of Industrial and Systems Engineers (IISE).Brahmastya Artanto is an undergraduate student of Industrial Engineering Department of Universitas SebelasMaret, Surakarta, Indonesia. He is also a research assistant at Logistics and Business Systems Laboratory inIndustrial Engineering Department. His research interests are supply chain management, logistics, business, technoeconomy, and sustainability. IEOM Society International2136
distribution route so that the distance of transportation decreases by about 60% than before. Keywords . Fuel, distribution route, vehicle routing problem . 1. Introduction . A company must be able to optimize its distribution system in order to compete with other similar companies. One way is by optimizing transportation.
