Decision Making: Applications in Management and Engineering Vol. 3, Issue 1, 2020, pp. 22-29. ISSN: 2560-6018 eISSN: 2620-0104 DOI: https://doi.org/10.31181/dmame2003132h * Corresponding author. E-mail addresses: omernuricam@gmail.com (Ö.N. Çam), kemal.sezen@altinbas.edu.tr (H.K. Sezen). The Formulation of a Linear Programming Model for the Vehicle Routing Problem in Order to Minimize Idle Time Ömer Nuri Çam 1 and Hayrettin Kemal Sezen 2* 1 Uludag University, Faculty of Economics and Administrative Sciences, Bursa, Turkey 2 Altınbaş University, School of Applied Sciences, Istanbul, Turkey Received: 15 August 2019; Accepted: 2 December 2019; Available online: 23 December 2019. Original scientific paper Abstract: The paper deals with the question, “What is the Vehicle Routing Problem, Which Is Minimized Idle Time, and How Its Linear Programming Model Is Written?” In this study, a linear programming (LP) model has been developed for the vehicle routing problem (VRP) in order to minimize the total idle time (MIT). This problem was realized while managing the route operations of a company transporting long-distance passengers by bus in Turkey. The differences between this problem and other VRPs first arise from its objective function. It suggests that vehicles should work more because they make profit if they work. So, its objective function should be defined so as to minimize the sum of the idle time of those vehicles. Contrary to the VR problems examined so far, vehicles should work more, sometimes preferring long-distance routes as well. The other two differences pertain to constraints: some locations should be visited more than once in different time periods, and subtours could be allowed in some situations. In order to present the problem, a total of 34 routes of the company which belongs to one of the five subgroups were chosen for the samples. To solve this kind of problems, it is very important that exact methods, such as linear programming or branch and bound, should be used. Keywords: vehicle routing problem; minimizing idle time; linear programming; location and time point. 1. Introduction The Vehicle Routing Problem (VRP) is an NP-Hard problem and is encountered in logistics management, which constitutes about 20% of product-service costs (Laporte, 2009). Researching VR problems grows 6% on average every year (Kramer et al., 2015) ⁠. mailto:omernuricam@gmail.com mailto:kemal.sezen@altinbas.edu.tr The Formulation of a Linear Programming Model for the Vehicle Routing Problem in... 23 The main components of the VRP are the geographical route network, the customer, the warehouse, vehicles and drivers. Different VRPs are distinguished according to these basic components by different constraints or types of routes. According to those components, the basic VRPs are divided into subcategories, such as capacity limited, distance constrained, time restricted, pick and delivery, open, mixed vehicles, partly carried, periodic, stochastic, fuzzy, green, and so on (Caceres- Cruz et al., 2014). ⁠ Day by day, new subcategories emerge, with different constraints and criteria representing real life. According to the literature, it can be said that it is impossible to directly classify some studies into one specific category. For this reason, Rich Vehicle Routing is proposed for solving multiple categories and constraints simultaneously (Caceres-Cruz et al., 2014) ⁠. Green vehicle routing can be seen as a new constraint to a reduction in carbon emissions and environmental pollution (Koç & Karaoglan, 2016) ⁠. VR problems are generally constraint satisfaction problems (CSP). Constraint satisfaction problems are combinatorial in their nature (Brailsford et al., 2019) ⁠. Since it is one of the NP-Hard type problems, heuristic algorithms are used extensively (Cordeau et al., 2007) ⁠. The objective functions of all problems are generally seen to minimize the costs of linking geographical resources to target points in previous research studies (Daneshzand, 2011; Braekers et al., 2015) ⁠. In the most general sense, VR problems are grouped as said above, but there is also a subproblem related to the definition of the hybrid elements of the basic VR problems (Kramer et al., 2015) ⁠. In this study, a new type of the objective function is presented and modeled, which will cast a different light on the aforementioned problems. The problem addressed is that it is different from other problems in terms of targeting the minimization of idle time for geographical points while offering a greater use of vehicles on their route. For this reason, the proposed name for the problem is VRPMIT (Vehicle Routing Problem Which Minimizes Idle Time). The objective function proposed in this study is similar to the sequencing problems with the minimum idle time in a job shop. The basic approach to the problem already considers each tool as a machine that should be used efficiently. In the literature, it is proposed that the same solution methods may be used because of the similarity of vehicle routing problems to scheduling problems, such as a job shop (Beck et al., 2003) ⁠. Vehicle scheduling algorithms can be considered as the top category of the VRP. At this stage, vehicles are listed according to dozens of constraints, such as working hours, employee permissions, official requests and customer needs, only to be followed by planning their routes. Generally speaking, routing is defined for the shortest route (Laporte, 2013) ⁠. At the same time, time window VRP problems were created by adding a time constraint to the problem (VRPTW). A vehicle must arrive in time and wait for the departure time at the arrival point (El-Sherbeny, 2010) ⁠. The main difference between this study and the VRPTW problem is that the whole route will be driven by one vehicle only, and if the departure time is missed, the vehicle will have to wait for the corresponding time next day. In vehicle scheduling problems similar to the scope of this study, it is proposed that public transport vehicles should be scheduled approximately according to customers’ needs. In such a study, the arrival-departure times at the stops can be stretched so that the lowest idle time occurs (Wang et al., 2017) ⁠. In this study, all trip times are assumed to be fixed and deterministic. When observing time-targeted or limited problems for the VRP, the literature gives short-term goals, such as the minimum driving salary and the minimum CO2 emissions Çam and Sezen/Decis.-Mak. Appl. Manag. Eng. 3 (1) (2020) 22-29 24 (Braekers et al., 2015) ⁠. It evaluates the issues such as time-related work, traffic conditions and vehicle maintenance, and presents sub-solutions with a certain or indeterminate arrival time. The outputs of these aims may generate similar results, but this study has a different perspective. The objective function addressed in the paper is a timed objective, which is ultimately aimed at achieving the minimum idle time of a vehicle, a device or equipment. From this point of view, vehicles should/may work for longer. As a result, the number of cars operated will be reduced, resulting in less waste in the resource use and increased operating efficiency. When looking at the previous research studies, the proposed solutions to VR problems are exact, heuristic and metaheuristic methods (Laporte, 2009) ⁠. There are many solutions using heuristic algorithms due to the easiness of finding a suitable solution (Daneshzand, 2011) ⁠. The solutions to be developed for the VRPMIT will be effected to direct and indirect costs, such as the number of vehicles, the fleet management, service/maintenance, ticket prices, carbon emissions, waste reduction in both land and airway operations. 2. The Definition of the Problem The company that provides passenger highway transportation by bus has the operation centers that coordinate and perform passenger transport operations in different settlement locations. These centers independently give their trip decisions related to their operations, can put new trips and cancel or take out the existing trip. A trip is the name of bus passenger transport from a settlement point (a location, called the origin) that will be travelled from at a certain time (the departure time) to another settlement point (the destination) at a certain time. When a bus completes this process, it waits until the most suitable departure time to move on to the target settlement point at this settlement point. This waiting period is called idle time. Figure 1 shows the route charts of one of the operation centers of the company on the map during the research period. The idle times between the trips are given in Table 1 and are expressed in minutes. Table 3 shows how these values are calculated. Figure 1. The route charts There can be multiple trips from a given geographical departure point, or more than one trips at different times. Each vehicle must end the complete route which The Formulation of a Linear Programming Model for the Vehicle Routing Problem in... 25 includes the tours within the subgroups. This tour is called the Mevlana tour organized by transport professionals. This problem implies that the company has five subgroups, our interest only being in one of them. Thus, we build a tour for one decision center including 34 trips. If we want to join all those subgroups together, we build a tour including about 500 trips. Historians called this type of long-distance tours Attila tours. Hence, costs might be lower and decision-making might be more effective. Figure 2 shows the trips managed by one of the company’s operation centers during the research period. Each arrow in the Figure represents one trip. Sp9 arc corresponds to sp9 (trip) in Table 2, which represents an expedition from Balıkesir at 8 am to the arrival time in Alanya at 10 pm, the journey lasting for approximately 14hours. When Figure 2 is examined, it is seen that there is only a two-way reciprocal trip to the both sides, but between Antalya and Izmir, and between Fethiye and İzmir, there are 6 two-way trips to the both sides reciprocally. Figure 1. An operation center’s trips Figure 2. As a TSP Çam and Sezen/Decis.-Mak. Appl. Manag. Eng. 3 (1) (2020) 22-29 26 In this problem, the aim is to minimize the sum of the idle times (waiting times) between the trips due to the time-dimensional connections of geographical points, taking into account the geographic boundaries, as well as the time dimension. Vehicles must make these trips as soon as possible and return to the starting point as they do in the Traveling Salesman Problem. The shortest time of all trips will ensure that the total duration of the tour is the smallest if there is no idle time. In this respect, the problem seems to be like the job shop scheduling problem as well. However, our problem may have sub-routes and some other VRP constraints. Table 1. The idle time between the trips; the table is trimmed for the purpose of gaining an easy insight into it Trip No sp1-9 sp10 sp11 sp12 sp13 sp14 sp15 sp16 sp17 sp18-34 sp1-9 ... sp10 X - - - - - - - sp11 - X - - - - - - sp12 - - X - - - - - sp13 - - - X - - - - sp14 - - - - X - - - sp15 - - - - - X - - sp16 1090 760 100 1300 1420 280 X - sp17 - - - - - - - X sp18-34 ... The data structure of this problem can be seen in Table 2. To make sure that a vehicle will return to the starting point, every trip needs to be reciprocal. Table 2. The data about the trips Trip Number City Departure City Destination Departure Time Duration Arrival Time sp9 Balıkesir Alanya 8 am 14 hours 10 pm sp23 Balıkesir Alanya 7 pm 14 hours 9 am sp15 Alanya Balıkesir 5 pm 14 hours 7 am sp11 Alanya Balıkesir 11 pm 14 hours 1 pm Total Time (T) 56 hours For the sake of clarity, the calculation of the VRPMIT is shown in Table 3. To provide one route, Tour I was randomly created from Table 2 as: sp23 – sp11 – sp9 – sp15 – sp23 Table 3. Tour I traveling and idle time Tour I Journey Number Arrival Time (A) Next Departure Time(D) Spare Time(D-A) 1 sp23 9 am 11 pm 14 hours 2 sp11 1 pm 8 am 19 hours 3 sp9 10 pm 5 pm 19 hours 4 sp15 7 am 7 pm 12 hours Total Idle Time (B) 64 hours The Formulation of a Linear Programming Model for the Vehicle Routing Problem in... 27 Efficiency Ratio: T / (T+B) 56/120=0.47 The efficiency ratio is about 47%. If the routing sequence is changed to be: sp23– sp15–sp9–sp11–sp23, Tour II is created in Table 4. Table 4. Tour II traveling and idle time Tour II Journey Number Arrival Time (A) Next Departure Time(D) Spare Time(A- D) 1 sp23 9 am 5 pm 8 hours 2 sp15 7 am 8 am 1 hour 3 sp9 10 pm 11 pm 1 hour 4 sp11 1 pm 7 pm 6 hours Total Idle Time (B) 16 hours Efficiency Ratio: T / (T+B) 56/72=0.78 As shown in Tables 3 and 4, the efficiency ratio rose to 78%. In Tour I (the first route), the total time was 120 hours, whereas the second route (Tour 2) only took 72 hours. A total of 48 hours was obtained, i.e. minimum two buses were saved by means of purchasing. The differences between the performance ratios show that it is very important to find a solution by an exact method, e.g. LP, DP, the Branch and Bound Technique… This sample problem is too small and there were not too many alternatives. Real-size problems, however, may be more complex and it might be impossible to find a solution by applying exact methods. 2.1. Solution Methods The discussed problem is an NP-hard, combinatorial type of problem. Different methods for solving such problems are proposed in the literature. Heuristic, metaheuristic methods, simulation methods generate solutions which are good enough, i.e. sufficiently close to the optimal solution, for which reason they can be considered as satisfactory. Moreover, simulation allows us to consider adding more different pillars to the model as well. It has been emphasized above how important using exact methods is for finding out a solution. Using mathematical programming methods, such as linear and dynamic programming, might allow us to find out the optimal solution. Backtracking and jumptracking, the two versions of the branch and bound technique, might also be very attractive for overcoming problems. When a problem grows in size, however, the effectiveness of the used method and the ability to reach the optimal solution rapidly diminish. 2.2. Linear Programming Model As is known, the VRP differs from the Traveling Salesman Problem (TSP) or Hamilton tours, especially so with respect to the fact that it has a larger number of routes. The standard objective function for the TSP is as follows: Min ∑ ∑ 𝑐ij 𝑛 𝑗≠i,j=0 𝑛 i=0 𝑥ij (1) where, cij is the cost from i to j; xij is the binary variable providing the information that the trip ended. Çam and Sezen/Decis.-Mak. Appl. Manag. Eng. 3 (1) (2020) 22-29 28 The objective function for the proposed VRPMIT aimed at finding the minimum idle time reads as follows: Min ∑ ∑ 𝑡ij 𝑛 𝑗≠i,j=0 𝑛 i=0 𝑥ij (2) where tij is the idle time. The constraints: Every trip should only be taken once: ∑ 𝑋i,j = 1 𝑛 𝑖 (3) ∑ 𝑋i,j = 1 𝑛 𝑗 (4) The limitations for the subtours optionally imposed: ∑ 𝑋i,i = 0 𝑛 𝑖 (5) 𝑋i,j + 𝑥j,i ≤ 1 (6) 𝑋i,j + 𝑥j,1+x1,i ≤ 2 (7) 𝑋i,j + 𝑥j,1 + ...+xz,i ≤ (𝑛 − 1) (8) and 𝑋i,j = 0 or 1 (9) i,j=1,2,...,n (10) Sometimes, subtours might be allowed in order to keep the cost lower. In this way, the problem further distances from the TSP. The foregoing model is quite similar to the job shop scheduling (sequencing) model, which considers n jobs and q machines in job shop (Sezen et al., 2017). 3. Conclusion Some solutions to the problem were found out by applying certain heuristic and backtracking methods. Some researchers work on solving the problem by applying mathematical programming, different branch and bound method applications, certain heuristic methods and simulation. Moreover, the use of these solutions as the core of the operational software related to transport companies, autonomous unmanned vehicles, and automatically controlled vehicles is the subject matter of future work. Another paper will deal with solving the LP model of the problem and discussing the result. Author Contributions: Each author has participated and contributed sufficiently to take public responsibility for appropriate portions of the content. Funding: This research received no external funding. Conflicts of Interest: The authors declare no conflicts of interest. The Formulation of a Linear Programming Model for the Vehicle Routing Problem in... 29 References Beck, J. C., Prosser, P., & Selensky, E. (2003). Vehicle Routing and Job Shop Scheduling : What’s the difference? Artificial intelligence, 267–276. Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2015). The vehicle routing problem: State of the art classification and review. Computers and Industrial Engineering, 99, 300–313. Brailsford, S.C., Potts, C.N. & Smith, B.M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119(3), 557– 581. Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., & Juan, A.A. (2014). Rich Vehicle Routing Problem. ACM Computing Surveys, 47(2), 1–28. Cordeau, J.-F., Laporte, G., Savelsbergh, M.W.P. & Vigo, D. (2007). Vehicle Routing. Transportation, 14, 367–428. Daneshzand, F. (2011). The Vehicle-Routing Problem. Elsevier. El-Sherbeny, N. A. (2010). Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University - Science, 22(3), 123–131. Koç Ç., & Karaoglan, I. (2016). The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing, 39, 154–164. Kramer, R., Maculan, N., Subramanian, A., & Vidal, T. (2015). A speed and departure time optimization algorithm for the pollution-routing problem. European Journal of Operational Research, 247(3), 782–787. Laporte, G. (2009). Fifty Years of Vehicle Routing. Transportation science, 43(4), 408– 416. Laporte, G. (2013). Scheduling issues in vehicle routing. Annals of Operations Research, 25(2), 1–12. Sezen, H.K., (2017). Yöneylem Araştırması, Dora Yayınevi, Baski, 3(1), 2-24. Wang, Y., Liao, Z., Tang, T., & Ning, B. (2017). Train scheduling and circulation planning in urban rail transit lines. Control Engineering Practice, 61, 112–123. © 2018 by the authors. Submitted for possible open access publication under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).