VRP-Spreadsheet-Solver-Solucao-de-Planilha-de-Codigo-Aberto-para-Problemas-de-Roteamento-de-Veiculos

Computers and Operations Research 84 2017 6272 Contents lists available at ScienceDirect Computers and Operations Research journal homepage wwwelseviercomlocatecor An open source Spreadsheet Solver for Vehicle Routing Problems Güne s Erdo gan School of Management University of Bath Bath BA2 7AY UK a r t i c l e i n f o Article history Received 17 November 2016 Revised 16 February 2017 Accepted 18 February 2017 Available online 16 March 2017 Keywords Vehicle Routing Problem Metaheuristics Spreadsheets Open source software a b s t r a c t The Vehicle Routing Problem VRP is one of the most frequently encountered optimization problems in logistics which aims to minimize the cost of transportation operations by a eet of vehicles operating out of a base This paper introduces VRP Spreadsheet Solver an open source Excel based tool for solving many variants of the Vehicle Routing Problem VRP Case studies of two realworld applications of the solver from the healthcare and tourism sectors that demonstrate its use are presented The solution algorithm for the solver and computational results on benchmark instances from the literature are provided The solver is found to be capable of solving Capacitated VRP and DistanceConstrained VRP instances with up to 200 customers within 1 h of CPU time 2017 The Author Published by Elsevier Ltd This is an open access article under the CC BY license httpcreativecommonsorglicensesby40 1 Introduction The Vehicle Routing Problem VRP is one of the most fre quently encountered optimization problems in logistics which aims to minimize the cost of transportation operations by a eet of vehicles operating out of a base called depot It arises in many industries and contexts at tactical and operational levels The VRP has been introduced more than 50 years ago by Dantzig and Ramser 1959 and many variants of the VRP that incorporate ad ditional features such as time windows intervals in which the cus tomers may be visited and eet composition Laporte 2009 have been studied Despite its operational nature the VRP is considered to be in the academic domain of Operations Research rather than Operations Management This is due to the inherent diculty of solving a VRP not only due to the complexity of the associated solution algorithms but also practical considerations regarding the implementation of the solution From a practitioners perspective there exist a number of bar riers to develop an inhouse VRP solver Developing a solution al gorithm for VRP is a daunting task and even if an opensource academic code is to be used as the solution algorithm most aca demics develop algorithms in C and the resulting codes are not designed for the fainthearted The travel distance and duration data have to be repeatedly retrieved from a GIS due to their dy namic nature which introduces either a recurring cost of acquisi tion or the requirement for inhouse specialist knowledge It is not straightforward to manually compute the existing cost of the vehi Email address GErdoganbathacuk cle routes much less so to visualize and compare the existing and optimized solutions which is important to demonstrate the benet of an optimization tool Although there exist many commercial software packages to solve VRPs any package must be integrated with the existing soft ware infrastructure of the company and needs to be learned by the planning managers Most commercial VRP software packages have a blackbox component the algorithm determining the vehi cle routes since the developers will want to protect their intellec tual property Finally every realworld application of the VRP has specic needs to which the software should be customtailored which requires a constant link with the company that developed it In case the company ceases to exist the software faces the risk to become obsolete in a few years In this study we introduce VRP Spreadsheet Solver that over comes the problems stated above through the familiarity of its interface ease of use exibility and accessibility Microsoft Ex cel is arguably the standard software for small to medium scale quantitative analysis for businesses and is being used in almost every corner of the world in both academia and industry alike Hesse and Scerno 2009 Many software packages have builtin functionality to exchange information with Excel which eases the integration of the solver The code for the solver developed us ing Visual Basic for Applications VBA is opensource and can be understood and modied by mediumlevel programmers VRP Spreadsheet Solver has builtin functions to query a GIS web ser vice from which the distances driving times and maps can be re trieved The solver is available for download on an academic web site at no cost Erdo ˇgan 2013 and has been downloaded over 20 0 0 times httpdxdoiorg101016jcor201702022 03050548 2017 The Author Published by Elsevier Ltd This is an open access article under the CC BY license httpcreativecommonsorglicensesby40 G Erdo gan Computers and Operations Research 84 2017 6272 63 VRP Spreadsheet Solver has been used in practice by multiple organizations in diverse sectors and countries The organizations that provided feedback include two US companies in the oil indus try an Argentinian company in the agriculture industry a Finnish company in the tourism sector and two chains of chilled food de livery in Taiwan and Turkey all of which report signicant savings We believe that VRP Spreadsheet Solver has the potential to be used throughout the world and achieve savings for many Small and Mediumsized Enterprises SMEs and consequently reduce CO 2 emissions Furthermore new VRP variants have emerged through our interaction with the users that are relevant to other sectors and they are our contribution to the literature The rest of this paper is organized as follows In Section 2 we provide a brief list of applications of the VRP In Section 3 we present two case studies of the application of VRP Spread sheet Solver and a resulting new VRP variant We provide a brief overview of how to use VRP Spreadsheet Solver in Section 4 In Section 5 we present a unied formulation that encompasses all variants of the VRP that VRP Spreadsheet Solver can handle a metaheuristic optimization algorithm that VRP Spreadsheet Solver utilizes and the results of VRP Spreadsheet Solver on a number of benchmark instances Finally in Section 6 we give our concluding remarks 2 Applications of the VRP With the progress of computer hardware and optimization soft ware better algorithms and implementations for the VRP emerge every year The computational reach of exact algorithms for the VRP is limited to 200 customers for the most studied basic vari ants of the VRP eg the columnandcut generation algorithm of Baldacci et al 2011 and decreases signicantly for more realistic variants that include features such as a heterogeneous eet or dis tance constraints On the other hand stateoftheart metaheuristic algorithms eg Adaptive Large Neighborhood Search Pisinger and Ropke 2007 Iterated Local Search Subramanian et al 2010 and Unied Hybrid Genetic Search Vidal et al 2014 can handle much larger instances and detailed operational constraints but cannot of fer a mathematical guarantee of performance As stated in the introduction many commercial and free solvers exist for the VRP A recent survey Partyka and Hall 2014 based on the answers to a questionnaire by 15 software vendors have provided a number of characteristics of available VRP software packages More recent surveys Bräysy and Hasle 2014 Wang et al 2015 list a number of commercial and free VRP software packages the latter including VRP Spreadsheet Solver and provide features required of VRP software packages We refer the interested reader to the comprehensive book of Toth and Vigo 2014 for criti cal reviews of many variants of the VRP and the associated solution algorithms In the rest of this section we provide a brief list of applications of the VRP The list is by no means complete but is provided to give an impression of the generality of VRP and the diversity of the industries and contexts it arises in The most straightforward appli cations of the VRP are found in the logistics sector Companies in the small package shipping industry for example aim to minimize the routing cost while keeping the routes of the drivers as consis tent as possible Groër et al 2009 A decision support tool uti lized by Toyota for selecting third party logistics service providers based on optimized vehicle routes is presented in Schittekat and Sörensen 2009 The problem of a large Benelux logistics service provider that aims to minimize the total transportation cost in a multidepot system which consists of the speedrelated distance related and vehiclerelated costs of transportation is analyzed in Demir et al 2014 Some examples of the VRPs arising in urban transportation are the ecient routing of the school buses Bekta s and Elmasta s 2007 and the design of tourist tours for visiting multiple points of interest in a city Gavalas et al 2014 The joint problem of bin allocation and vehicle routing to optimize solid waste collection is studied in Hemmelmayr et al 2014 There is also a growing body of literature on optimizing the rebalancing operations for shared bicycle systems that aim to minimize the total cost and maximize the user satisfaction Forma et al 2015 The importance of the use of VRP models in humanitarian logistics have been underlined in the survey by Van Wassen hove 2006 Optimizing postdisaster relief operations by min imizing estimated total travel time of vehicles is studied in Özdamar and Demir 2012 The problem of nding the optimal routes for teams that survey a disaster area to assess damage and relief needs is analyzed in Huang et al 2013 Planning of fuel dis tribution operations in the case of a domestic disaster is studied in Nerg and Stuckenschneider 2014 where the authors use VRP Spreadsheet Solver to optimize the routes With the increasing emphasis on climate change and environ mental concerns a venue of research within the VRP has emerged in the past decade named as Green Vehicle Routing Problems G VRP The objective function of these problems focus on minimiz ing CO 2 emissions noise pollution and accidents as stated in the recent survey on GVRP Eglese and Bekta s 2014 The problem of minimizing the risk of running out of fuel which is prominent in the route planning for Alternative Fuel Vehicles is studied by Erdo ˇgan and MillerHooks 2012 The problem of determining the optimal size and mix of a vehicle eet of electric vehicles is ana lyzed by Hiermann et al 2016 Applications of the VRP are not limited to companies with a sole focus on logistics Indeed variants of VRP may arise in any context where a pickup or delivery service is performed Specif ically examples from the healthcare sector include routing of nurses for home health care Mankowska et al 2014 and the transportation of blood donations to storage centers S ahinyazan et al 2015 Yi 2003 and the delivery services for biological samples collected from patients to testing laboratories Andrade Pineda et al 2013 3 Case studies VRP Spreadsheet Solver can solve more than 64 variants of the VRP based on features related to selective visits to customers si multaneous pickups and deliveries time windows eet compo sition distance constraint and the nal destination of the vehi cles Some of these variants are relevant in practice but have not been formally studied VRP Spreadsheet Solver can hence provide a starting point and a benchmark result for future studies on such problems In the rest of the section we go over two case studies in which VRP Spreadsheet Solver was used and a new VRP variant that we introduce as a result 31 Healthcare sector A nonprot organization based in Istanbul Turkey provides a set of healthcare services at home including visits by medical doctors and nurses providing physiotherapy and psychotherapy as well as logistic services such as patient transport domestic clean ing and personal hygiene The services are performed at no cost and are provided for the poor elderly and disabled citizens The number of registered patients is over 30 0 0 and an average of 10 0 0 patients in separate locations are served each day The organization operates out of three bases and owns a eet of 90 vehicles each of which can by driven by the health specialists and contains a small medical inventory 64 G Erdo gan Computers and Operations Research 84 2017 6272 Fig 1 Visualization of the result for the case study in the healthcare sector The logistics planning manager of the organization intended to use the nurse service as a test case for VRP Spreadsheet Solver and apply it to the planning of other services if the results were suc cessful This service operates out of one of the bases on the Ana tolian side of the city with 20 vehicles and serves 150 patients per day on the average The visits are planned in advance with no time window specied and all patients scheduled for a visit on a given day must be visited The service time per patient although there are slight variations was assumed to be constant The vehicles are refueled during the night and their range is enough to cover a day trip so the distance limit is not a binding constraint Even though the vehicles are from different makers and models they are con sidered identical in terms of operational parameters Each nurse has a driving time limit of 8 h as per the general regulations about driving and a working time limit of 9 h including the lunch break Capacity of the vehicles does not seem to be a binding con straint since there is no patient transport service involved and the medical supplies in a vehicle can last a day However concerns of equal work allocation to the nurses were brought up that were not addressed by the working time limit Given the size of the city and heavy trac a solution may contain routes with long driving times and a small number of patient visits and other routes with short driving times and a signicantly larger number of visits To pro hibit unequal work distribution in terms of patients visited each vehicle was assigned a capacity that is slightly larger than the ratio of the number of patients to be served to the number of vehicles and each patient location was assigned a demand value of 1 Initial runs with this setting seemed to satisfy the workload eq uity concerns However problems with the solution were realized upon a detailed analysis of the results The driving durations re trieved from the GIS web service are based on using the main ar teries of the transportation infrastructure ie highways and al though the speed of transportation on the arteries are acceptable getting into and out of the arteries is time consuming Hence a so lution that visits multiple districts of the city accumulates a higher driving time than the GIS driving durations provide To overcome this problem the users at the organization modied the driving durations by adding a penalty term to the durations between lo cations in separate districts to prohibit the routes from changing districts multiple times After a few experiments with this penalty parameter the users found a setting for which the resulting routes were observed to be more realistic The visualization of the result ing solution for a day with 150 patient locations is provided in Fig 1 The return arcs to the depot are omitted for a clearer vi sualization The organization refrained from providing gures regarding cost savings but the feedback indicated that the planning process was more transparent to their staff and the use of the tool increased their awareness of the ner details of the transportation compo nent of their operation This case study serves to show that the decision makers often have managerial concerns that are not di rectly addressed in the routing literature the GIS data may not give an accurate reection of the reality and parameters of VRP Spreadsheet Solver can be used to generate solutions that can ad dress managerial concerns as well as shortcomings of the available data 32 Tourism sector A tourism company based in Finland offers numerous types of travel packages the main one being a ferry trip between the cities of Helsinki and Tallinn Estonia The customers use the ferry for a day trip or an overnight visit to Tallinn or to other cities in Esto nia Baltic countries for 17 days These routes are operated from 4 to 7 days during the week depending on the season The com pany aims to maximize protability by planning the travel pack ages based on demand forecasts and vehicle capacities A signi cant portion of their cost is due to the bus service they outsource from subcontractors to pick up customers from their houses on the morning of their trip and return them back to their houses at the end of their trip The buses subcontracted by the company are based in 7 de pots one of them in Helsinki The buses are of different models and make and can have different carrying capacities The subcon tractors charge a xed price per day of use so the problem be comes minimizing the number of buses needed a problem of pack ing as well as routing The customers need to be at the ferry ter minal in Helsinki 15 min before the ferry departs and some depots are located quite far away from Helsinki which pushes the driving time and working time limits to be binding constraints There are no time windows for the customers and all locations containing customers must be serviced The buses based in Helsinki perform closed tours in which they pick up customers and return to the ferry port On the other hand the buses based at the other depots perform open tours ie nish their trip in a location that is not their depot These buses eventually go back to their respective de pots using the exact same route traversed in the reverse direction A sample solution is depicted in Fig 2 where locations that do not contain any customers are not visited The problem at hand is then an instance of the CloseOpen Mixed Vehicle Routing Problem COMVRP introduced in Liu and Jiang 2012 We agree with the authors of this paper that the COMVRP has applications in many sectors in which the transporta tion service is subcontracted to companies based at multiple cities An extension of the COMVRP is the CloseOpen Mixed Team Ori enteering Problem in which the customers are serviced selectively based on the capacity and the distance limit of the vehicles A for mulation that is capable of solving both these new variants as well as others is presented in Section 5 4 How to use VRP Spreadsheet Solver In this section we will briey describe the structure of the worksheets and the menu of VRP Spreadsheet Solver We will be focusing on its usability rather than the technical details for which the interested user can refer to the users manual G Erdo gan Computers and Operations Research 84 2017 6272 65 Fig 2 Visualization of the result for the case study in the tourism sector 41 Structure of the spreadsheets VRP Spreadsheet Solver keeps the data about the elements of a VRP in separate worksheets and adopts an incremental ow of information Initially the workbook only contains the worksheet named VRP Solver Console The remaining worksheets 1Locations 2Distances 3Vehicles 4Solution and 5Visualization are gener ated in the sequence denoted by their indices Fig 3 depicts the information ow between the spreadsheets where the arrows sig nify the dependence of a worksheet on another worksheet To guide the user about which cells of a spreadsheet to work on we have adopted the following color scheme The cells with a black background are set by the worksheets and should not be modied The cells with a green background are parameters or de cisions to be set by the user The cells with a yellow background are to be computed by the worksheets but they can be edited by the user for whatif analysis The cells with an orange background signal a warning eg a vehicle arriving before the beginning of the time window of a customer The cells with a red background signal an error eg a vehicle violating the capacity constraint The work sheets described below utilize this color scheme 411 VRP Solver Console This worksheet stores and provides information to the rest of worksheets It contains various parameters regarding the size of the instance being solved and its characteristics including the number of depots and customers number of vehicle types the width of time windows In addition the user can set the options about GIS data retrieval and the time that the user allows the solver to work on the problem A screenshot of the worksheet is presented in Fig 4 412 1Locations The details about the locations including their names ad dresses coordinates time windows and pickup and delivery ser vice requirements are kept in this worksheet The coordinates can be input manually or copied and pasted from an external source or populated using the GIS web service based on the addresses in put by the user It is good practice to provide a postcode with ev ery address since vague addresses may correspond to unreachable points eg the address of a park being resolved to be in the middle of a lake It is possible to prohibit the vehicles from visiting certain customers using the options in this worksheet for quick whatif analysis without data modication Fig 5 displays a screenshot of the worksheet 413 2Distances This worksheet contains the distances and travel durations be tween every two points that are specied in the 1Locations work sheet As of the time of this writing using the GIS web service to populate the distances and driving distances takes about 5 min for 50 locations and 45 min for 150 locations The number of lo cations for which the distance matrix can be computed is limited by the GIS web service and the type of access the user has to it VRP Spreadsheet Solver provides an estimate the time requirement for this step by simply multiplying the number of entries in the distance matrix by a factor of 01 s The parameter about the type of route shortest or fastest is crucial Choosing the shortest route usually nds routes that go through city centers which are subject to strict speed limits and heavy trac Hence using the fastest route is usually a better option for large distance delivery operations On the other hand fastest routes may end up using peripheral highways of the city too frequently and consequently the shortest paths may be bet ter suited to companies performing intracity delivery operations It is also possible to retrieve realtime driving durations based on the trac which is computed and provided by the GIS web ser vice The user can prohibit the vehicles from traveling between two given locations by manually setting the relevant distance to a high value A screenshot of the 2Distances worksheet is depicted in Fig 6 414 3Vehicles The data about the vehicle types are kept in this worksheet The user can set the number of vehicles of each type that are kept at each depot The data includes cost parameters such as the cost per unit distance and the cost per trip as well as operational param eters eg the depot capacity driving time limit and the distance limit of the vehicle Only one capacity parameter exists which may correspond to the weight capacity of trucks in the case of an exca vation operation the volume capacity of tanker trucks in the case of oil transport or the maximum number of passengers in the case of school bus routing Fig 7 displays a screenshot of the worksheet Fig 3 Spreadsheet structure of VRP Spreadsheet Solver 66 G Erdo gan Computers and Operations Research 84 2017 6272 Fig 4 VRP Solver Console spreadsheet Fig 5 1Locations spreadsheet Fig 6 2Distances spreadsheet Fig 7 3Vehicles spreadsheet G Erdo gan Computers and Operations Research 84 2017 6272 67 Fig 8 4Solution spreadsheet 415 4Solution This worksheet is generated to contain the list of stops for each vehicle specied in 3Vehicles and it uses the information in 1Lo cations to regarding service times and pickup delivery amounts as well as the distance and duration in 2Distances to compute the departure arrival times the cost of traveling between customers The worksheet computes the net prot rather than cost to ac commodate variants of the VRP that accumulate prots when cus tomers are selectively visited This worksheet contains a number of conditional formatting features that are designed to visually iden tify infeasible solutions and facilitate manual solution construction For example a vehicle exceeding its capacity or distance limit or a customer being visited out of its time window are highlighted in red It is also possible to copy and paste lists of customers be tween vehicle routes for the purpose of manual modication of the routes A screenshot of the 4Solution worksheet is provided in Fig 8 416 5Visualization The locations and the routes of the vehicles can be visually in spected by generating this optional worksheet Options in the VRP Solver Console may be set to display various details about the lo cations including their pickup delivery amounts or service times This worksheet simply contains a scatter graph with the map of the region retrieved from the GIS web service It can be formatted eg made smaller or larger or display axes for the needs of the user as any other graph object of Excel Fig 9 displays a screen shot of the worksheet 42 Structure of the menu of VRP Spreadsheet Solver The menu is located in the Addins tab of the ribbon and consists of 5 core and 3 optional commands to set up the work sheets It also includes the command to engage the solver as well the optional calls to a feasibility checker for manually modied so lutions and an external solver that advanced users may develop and compile into a Dynamically Linked Library DLL le The nu merical indices of the commands match the numerical indices of the worksheets for ease of use Fig 10 5 A unied formulation for the VRP and the solution algorithm The eld of VRP research is mature and many solution al gorithms have been developed The best known heuristic algo rithm is arguably the savings algorithm Clarke and Wright 1964 Many metaheuristic algorithms have been proposed in the last decade the most successful being the Adaptive Large Neighbor hood Search Pisinger and Ropke 2007 Iterated Local Search Subramanian et al 2010 and Genetic Algorithms Vidal et al 2014 In the rest of this section we provide a unied formula tion for the VRP that encompasses all variants of the VRP that VRP Spreadsheet Solver can handle the pseudocode of the metaheuris tic solution algorithm implemented with VRP Spreadsheet Solver the details of how the infeasible solutions are handled and the computational results of our algorithm on benchmark instances 51 A unified formulation for the VRP We rst provide the notation that we will use to state the for mulation Let us dene the vertex set V D to contain the depots V C to contain the customers and V V D V C Furthermore we dene V M V C as the set of customers that must be visited Let G V A be the complete directed network on which we will solve the VRP We dene the prot of servicing a customer i V C as p i the pickup service amount for the customer as q i the delivery service amount as ˆ q i and the service time required by the customer as s i Further more we dene the time interval for the customer as a i b i Note that there is also a time interval for each depot vertex Let us denote the set of vehicles as K and dene for each ve hicle k K the origin depot of the vehicle as o k V D the work start time of the vehicle as τ k the xed cost of using the vehicle as f k the capacity of the vehicle as Q k the distance limit as D k the driving time limit as ˆ D k the working time limit as W k and the re turn depot of the vehicle as r k Associated with each arc i j A there is a distance d ij and driving duration ˆ d ij In addition for each vehicle k K there is a travel cost c k ij on arc i j Next we present the parameters related to the operational con straints Let us dene to be equal to 1 if the vehicles have to return to their specied return depots and 0 otherwise Similarly let us dene β to be 1 if there is a backhaul constraint and 0 oth erwise In addition we dene to be equal to 1 if the time win dows can be violated at the cost of a penalty per unit time and 0 otherwise We are now ready to dene the decision variables Let x k ij be equal to 1 if vehicle k traverses arc i j and 0 otherwise Further more let y k i be equal to 1 if vehicle k visits and serves vertex i and 0 otherwise The amount of the pickup commodity and the deliv ery commodity carried by vehicle k on arc i j is dened as w k ij and z k ij respectively We also dene t k i as the time at which vehicle k arrives at vertex i and v i as the amount of violation of the time 68 G Erdo gan Computers and Operations Research 84 2017 6272 Fig 9 5Visualization spreadsheet Fig 10 VRP Spreadsheet Solver menu window of vertex i The formulation for the unied VRP is then Maximize i V C k K p i y k i ij A k K c k ij x k ij j V C k K f k x k o k j i V v i 1 subject to k K y k i 1 i V M 2 k K y k i 1 i V C V M 3 j V i x k ij j V i x k ji j V C k K 4 p Sq V S x k pq y k i i V C k K S V o k S i V S 5 p Sq V S x k pq y k i i V C k K S V i S r k V S 6 j V C x k o k j 1 k K 7 k K x k ij 1 β i j A q i 0 and ˆ q j 0 8 j V i w k ij j V i w k ji q i y k i i V C k K 9 i V C w k ir k j V C q j y k j k K 10 G Erdo gan Computers and Operations Research 84 2017 6272 69 j V i z k ji j V i z k ij ˆ q i y k i i V C k K 11 i V C z k o k j i V C ˆ q i y k i k K 12 t k i ˆ d ij s i x k ij W k 1 x k ij t k j i j A j V C k K 13 a i t k i b i s i v i i V C k K 14 v i M i V C 15 t k o k τ k k K 16 t k i s i ˆ d ij x k ir k b r k v r k M1 i j A i V C k K 17 w k ij z k ij Q k x k ij i j A k K 18 ij A d ij x k ij D k i j A k K 19 ij A ˆ d ij x k ij ˆ D k i j A k K 20 i V C s i y k i i j A ˆ d ij x k ij W k i j A k K 21 x k ij 0 1 i j A k K 22 y k i 0 1 i V C k K 23 v i 0 i V C 24 w k ij 0 i j A k K 25 z k ij 0 i j A k K 26 The objective function 1 maximizes the total prot collected minus the travel cost of vehicles xed cost of using vehicles and the penalty for violating time windows We rst state the con straints set the visit rules for the customers by the vehicles Con straint 3 enforces a visit to the customers that must be visited and constraint 2 ensures that every customer is visited at most once Constraint set 4 is a weak form of the wellknown ow conservation constraints which require an inow if there is an outow and accommodates the VRP variants in which the vehicle does not have to return to its depot Constraints 5 provide the connectivity between the origin depot of vehicle k and the cus tomers visited by this vehicle and constraints 6 dictate the vehi cle to return to its depot if it is required to Constraints 7 state that each vehicle can be used at most once whereas the backhaul constraint is enforced by constraint 8 Next we present the constraints that set the customer require ments The ow conservation for the pickup commodity is pro vided by constraints 9 and 10 Similarly the ow conservation for the delivery commodity is provided by constraints 11 and 12 Constraints 13 are formulated based on the MillerTucker Zemlin subtour elimination constraints Miller et al 1960 and provide the framework for the time windows The lower and upper limits of the time window for each customer and the variable to account for violation are stated in constraints 14 and 15 The nal set of constraints state the restrictions related to ve hicles Constraints 16 and 17 set the start of the working time for vehicle k and ensures that the vehicle returns to its depot on time if it is required to Constraint 18 prohibit the violation of the vehicle capacities Constraints 1921 state the distance driving time and working time limits for each vehicle respectively Fi nally constraints 22 26 are integrality and nonnegativity con straints To the best of our knowledge there has not been any attempts to formulate a VRP with all the constraints stated above Although the formulation can be solved to optimality only for small in stances it denes the problem precisely demonstrates its com plexity and will serve as a reference formulation for the future studies on the VRP Next we provide our algorithm to solve this formulation 52 Pseudocode of the solution algorithm We have opted to implement a variant of the Adaptive Large Neighborhood Search of Pisinger and Ropke 2007 within VRP Spreadsheet Solver due to its exibility to accommodate many variants of the VRP The algorithm diversies the search by ran domly removing customers from the solution at hand and intensi es through reinsertion of the customers and local search A high level pseudocode is provided below named as Algorithm 1 Algorithm 1 LNS algorithm implemented within VRP Spreadsheet Solver 1 procedure LNSdepots customers distances durations vehi cles 2 Construct an incumbent solution by adding customers to the routes choosing the customer that results in the maximal prot increase equivalently minimal cost increase at every step 3 Improve the incumbent solution using local search with the EX CHANGE 1OPT 2OPT and VEHICLEEXCHANGE operators 4 Record the incumbent solution as the best known solution 5 repeat 6 Destroy the incumbent solution by randomly removing ver tices 7 Repair the incumbent solution heuristically by adding ver tices 8 Improve the incumbent solution using local search with the EXCHANGE 1OPT 2OPT and VEHICLEEXCHANGE operators 9 if the incumbent solution is better than the best known solu tion then 10 Record the incumbent solution as the best known solution 11 else 12 Replace the incumbent solution by the best known solution with probability p 13 until time elapsed is larger than the CPU time allowed 14 return best known solution 15 end LNS 70 G Erdo gan Computers and Operations Research 84 2017 6272 Four local search operators have been utilized in Algorithm 1 namely EXCHANGE 1OPT 2OPT and VEHICLEEXCHANGE The EXCHANGE operator searches all possible pairs of customers in a given solution and checks if exchanging them would result in a better objective function value The operator 1OPT examines the possibility of removing every customer within a given solution and reinserting it to a different position within the routes to improve the objective value The 2OPT operator attempts to remove two arcs from the solution at a time eg the arc from customer a to customer b and the arc from customer c to customer d To retain feasibility it then adds the arc from customer a to customer d and the arc from customer c to customer b and checks if the result ing solution has a better objective value All three operators de scribed so far have a neighborhood size of O V 2 and we refer the interested reader to the review by Groër et al 2010 for their details The operator VEHICLEEXCHANGE attempts to exchange all the customers in the routes of two vehicles with different types has a neighborhood size of O K 2 and is particularly useful for the case of heterogeneous eets Two constructive heuristics are employed in step 7 are greedy insertion and max regret The latter heuristic is based on select ing the customer for which the difference between the cost of the cheapest insertion and the second cheapest insertion decisions is the largest Both heuristics are chosen with equal probability at each iteration Each heuristic nds a number of best candidates a parameter set by the algorithm and chooses randomly among them at each step The probability p of rejecting an incumbent so lution is set at 10 in the beginning and decreases linearly with time to reach 0 at the end of the CPU time allowance 53 Handling infeasibility Infeasibility of a solution refers to the case when one or more constraints are violated by a solution whereas infeasibility of an instance refers to the case when it is not possible to nd any fea sible solution for the instance Infeasibility is a common occurrence in the eld of algorithm development However a software pack age that returns an infeasibility message with no suggestions for remedial action is of little use to a practitioner and the computer or real time spent waiting for the result is perceived as wasted time Mathematically a solution is either feasible or infeasible and there is no comparison between two infeasible solutions However many solutions that would be declared infeasible by a computer could be useful in practice For example an infeasible solution with a single route exceeding the capacity of the vehicle by a fraction of the vehicle capacity can be converted into a feasible one by rene gotiating the delivery amount with a customer on the route Simi larly a vehicle exceeding the working time limit can be made fea sible by paying the driver for the extra time As a consequence all solutions may be infeasible but in practice some are less infeasi ble This gives rise to the need of a method of penalizing infeasi bility based on its severity An intuitive way of penalizing infeasibility is to include it into the objective function with a penalty coecient Let us denote the capacity of a vehicle in a homogeneous eet by Q the ca pacity required for route to be Q and the penalty coecient to be a large constant M We then need to include a penalty term of max Q Q 0 M to the objective function to ensure that vi olating the capacity constraint will be penalized However mini mizing this term does not necessarily make the resulting solution useful Consider the case with k vehicles of capacity Q and a num ber of customers with a total demand of k 1 Q In this case the penalty value of a solution with the rst vehicle containing 2 Q units and the rest of the vehicles containing Q units is equal to the penalty value of a second solution with all vehicles carrying Q 1 units However many practitioners would nd the latter solution to be more useful since there is a smaller degree of modication required on each vehicle route The only hard constraint within the solution algorithm of VRP Spreadsheet Solver is to visit customers that must be visited and this constraint is enforced on all solutions throughout the algo rithm The rest of the constraints are all treated as soft constraints and their violations are penalized To prioritize infeasible solu tions with less severe violations the solution algorithm uses a quadratic scaling method for the penalty Following the example in the previous paragraph the penalty term for a vehicle would be max Q Q 0 Q 2 M As a result a violation of the capacity constraint by 5 of the capacity would be penalized by 00025 M whereas a violation of 10 would be penalized by 001 M Simi lar formulas apply for the violation of the time windows distance limit driving time limit and working time limit The solver component of VRP Spreadsheet Solver rst performs a feasibility check of the data and searches for possible reasons of infeasibility The search entails customers that must be visited but cannot be reached or serviced by any vehicle within the given time limit as well as pickup delivery amounts that cannot t in any of the vehicle types It also compares the overall carrying capacity of the eet to the total pickup delivery requirement of the cus tomers If any of these issues are found the user is alerted with a message and given a choice to stop or proceed If the user decides to proceed the resulting solution will certainly be infeasible but may still be useful 54 Computational results on benchmark instances Before presenting our computational results on benchmark in stances we would like to make a brief comparison of the computa tional tests carried out in the routing literature and the use of VRP optimization software in practice The academic studies are usually run on a stateofthe art computer dedicated to the task with the algorithms coded in C Additionally the academic studies limit the CPU time by restricting the algorithm a number of iterations which may result in different CPU times on different computers On the other hand a practitioner is more likely to run the VRP optimization algorithm on an ordinary laptop computer possibly with other programs running in the background Furthermore a practitioner will need a solution in a given amount of time since the output of the software will be an input of the decision process rather than its result We also would like to emphasize that the speed of VBA is or ders of magnitude lower than that of C To the best of our knowledge there is no academic source that provides a speed comparison so we have performed the following small experiment We have created an array of integers with 100 0 0 elements and we have lled this array with U 0 1 10 0 0 and repeated this process 100 0 0 times On the average of 10 runs of this small pro gram C implementation of this small program has taken 156 s whereas the VBA implementation has required 420 s approxi mately 27 times that of C In terms of memory management and pointers C is known to be very ecient the importance of which is realized for problems with large memory requirements and results in larger performance deviations Based on the reasons stated above we have decided to test the solution algorithm using a laptop computer with an Intel i7 CPU running at 25 GHz with 8 GB of RAM a conguration that would reect the computers used in practice We have set the CPU time limit for the solution algorithm VRP Spreadsheet Solver to 15 min for instances with 50 customers and increased it lin early with the number of customers for larger instances We do not claim that a single algorithm can solve all the variants of the VRP to nearoptimality and we believe that a computational G Erdo gan Computers and Operations Research 84 2017 6272 71 Table 1 Computational results on benchmark instances Instance Number of Fleet size Vehicle Distance Best known VRP Spreadsheet Solver name customers capacity limit solution value Average Average gap Best Best gap vrpnc1 50 5 160 NA 52461 52461 000 52461 000 vrpnc2 75 10 140 NA 83526 84067 065 83526 000 vrpnc3 100 8 200 NA 82614 84105 180 83128 062 vrpnc4 150 12 200 NA 102842 105222 231 104081 120 vrpnc5 199 17 200 NA 129129 134119 386 132308 246 vrpnc6 50 6 160 200 55543 55677 024 55543 000 vrpnc7 75 11 140 160 90968 91313 038 90968 000 vrpnc8 100 9 200 230 86594 87640 121 86594 000 vrpnc9 150 14 200 200 116255 118177 165 117081 071 vrpnc10 199 18 200 200 139585 143527 282 141502 137 vrpnc11 120 7 200 NA 104211 104782 055 104761 053 vrpnc12 100 10 200 NA 81956 82129 021 82129 021 vrpnc13 120 11 200 720 154114 156501 155 155451 087 vrpnc14 100 11 200 1040 86637 88641 231 86996 041 experiment to solve all existing variants is beyond the scope of this paper Hence we have opted to use the wellknown and widely used benchmark data set by Christodes et al 1981 that contains two of the main variants of the VRP the Capacitated VRP and the Distance Constrained VRP The computational results are provided in Table 1 and show that the algorithm performs very well for up to 100 customers and returns acceptable results for larger instances The performance of the algorithm is better for instances with a distance constraint due to the reduced search space The performance is slightly degraded for the last four instances which consist of articially constructed clusters of customers We recommend a larger CPU time allowance for such instances A copy of VRP Spreadsheet Solver containing a realworld PickupandDelivery VRP instance with 27 customer locations has been made available for researchers to verify the solution algo rithm and use the instance as a benchmark for future studies Erdo ˇgan 2017 As a nal note we would like to state that we welcome contributions from the researchers developing algorithms for the VRP in the form of DLL les containing their solution algo rithms Contributed implementations will be hosted online jointly with VRP Spreadsheet Solver with the full credit of each DLL le being attributed to the researchers who contributed it 6 Concluding remarks In this paper we have introduced VRP Spreadsheet Solver an open source s preadsheet s olver for the VRP and its many variants We have demonstrated its realized and potential benets on two case studies one from the healthcare sector and the other one from the tourism sector We have shown the performance of the solution algorithm on a set of benchmark instances from the lit erature We believe that VRP Spreadsheet Solver has the potential to be used throughout the world due to its ease of use exibil ity and accessibility and achieve savings for many SMEs as well as CO 2 emissions Any decision support tool should be able to generate alternative solutions for the decision maker VRP Spreadsheet Solver currently returns and displays a single solution for the sake of simplicity As future work we plan to add a parameter for the number of alternative solutions required by the user record the corresponding number of best solutions encountered during the solver run and return the results Acknowledgment We thank Maria Battarra for her constructive comments on a draft of this paper Thanks are also due to the two anonymous re viewers whose comments have helped to improve the paper Fi nally this study has been partially supported by the Impact Devel opment Grant of School of Management University of Bath This support is gratefully acknowledged References AndradePineda JL GonzalezR PL Framinan JM 2013 A decisionmaking tool for a regional network of clinical laboratories Interfaces 43 4 360372 Baldacci R Mingozzi A Roberti R 2011 New route relaxation and pricing strate gies for the vehicle routing problem Oper Res 59 5 12691283 Bekta s T Elmasta s S 2007 Solving school bus routing problems through integer programming J Oper Res Soc 58 12 15991604 Bräysy O Hasle G 2014 Software tools and emerging technologies for vehicle routing and intermodal transportation In Toth P Vigo D Eds Vehicle Rout ing Problems Methods and Applications 18 SIAM pp 351380 Christodes N Mingozzi A Toth P 1981 Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxations Math Program 20 1 255282 Clarke G Wright JW 1964 Scheduling of vehicles from a central depot to a num ber of delivery points Oper Res 12 4 568581 Dantzig GB Ramser JH 1959 The truck dispatching problem Manage Sci 6 1 8091 Demir E Woensel TV de Kok T 2014 Multidepot distribution planning at logis tics service provider nabuurs bv Interfaces 44 6 591604 Eglese R Bekta s T 2014 Green vehicle routing In Toth P Vigo D Eds Vehicle Routing Problems Methods and Applications 18 SIAM pp 437458 Erdo ˇgan G 2017 Glasgow Bike Share Rebalancing Problem Data in Brief Submit ted Erdo ˇgan G 2013 VRP Spreadsheet Solver Available for download at httpverolog deisuniboitvrp spreadsheet solver Erdo ˇgan S MillerHooks E 2012 A green vehicle routing problem Transp Res Part E 48 1 100114 Forma IA Raviv T Tzur M 2015 A 3step math heuristic for the static reposi tioning problem in bikesharing systems Transp Res Part B 71 230247 Gavalas D Konstantopoulos C Mastakas K Pantziou G 2014 A survey on algo rithmic approaches for solving tourist trip design problems J Heuristics 20 3 291328 Groër C Golden B Wasil E 2009 The consistent vehicle routing problem Manuf Serv Oper Manage 11 4 630643 Groër C Golden B Wasil E 2010 A library of local search heuristics for the ve hicle routing problem Math Program Comput 2 2 79101 Hemmelmayr VC Doerner KF Hartl RF Vigo D 2014 Models and algorithms for the integrated planning of bin allocation and vehicle routing in solid waste management Transp Sci 48 1 103120 Hesse R Scerno DH 2009 How electronic spreadsheets changed the world In terfaces 39 2 159167 Hiermann G Puchinger J Ropke S Hartl RF 2016 The electric eet size and mix vehicle routing problem with time windows and recharging stations Eur J Oper Res 252 3 9951018 Huang M Smilowitz KR k BB 2013 A continuous approximation approach for assessment routing in disaster relief Transp Res Part B 50 2041 Laporte G 2009 Fifty years of vehicle routing Transp Sci 43 4 408416 Liu R Jiang Z 2012 The closeopen mixed vehicle routing problem Eur J Oper Res 220 2 349360 Mankowska DS Meisel F Bierwirth C 2014 The home health care routing and scheduling problem with interdependent services Health Care Manage Sci 17 1 1530 Miller CE Tucker A W Zemlin RA 1960 Integer programming formulation of traveling salesman problems J ACM 7 4 326329 72 G Erdo gan Computers and Operations Research 84 2017 6272 Nerg A Stuckenschneider K 2014 Domestic Disasters and Geospatial Technology for the Defense Logistics Agency Naval Postgraduate School Monterey Califor nia MBA thesis Özdamar L Demir O 2012 A hierarchical clustering and routing procedure for large scale disaster relief logistics planning Transp Res Part E 48 3 591 602 Partyka J Hall R 2014 Vehicle routing software survey VR delivers the goods ORMS Today 41 4046 Pisinger D Ropke S 2007 A general heuristic for vehicle routing problems Com put Oper Res 34 8 24032435 S ahinyazan FG Kara BY Taner MR 2015 Selective vehicle routing for a mobile blood donation system Eur J Oper Res 245 1 2234 Schittekat P Sörensen K 2009 OR Practicesupporting 3PL decisions in the auto motive industry by generating diverse solutions to a largescale locationrouting problem Oper Res 57 5 10581067 Subramanian A Drummond LMA Bentes C Ochi LS Farias R 2010 A parallel heuristic for the vehicle routing problem with simultaneous pickup and deliv ery Comput Oper Res 37 11 18991911 Toth P Vigo D 2014 Vehicle routing problems methods and applications SIAM 18 Van Wassenhove NL 2006 Humanitarian aid logistics supply chain management in high gear J Oper Res Soc 57 5 475489 Vidal T Crainic TG Gendreau M Prins C 2014 A unied solution framework for multiattribute vehicle routing problems Eur J Oper Res 234 3 658673 Wang X Battarra M Golden B Wasil E 2015 Vehicle routing and scheduling In Teodorovic D Ed The Routledge Handbook of Transportation Routledge London U K pp 238256 Yi J 2003 Vehicle routing with time windows and timedependent rewards a problem from the american red cross Manuf Serv Oper Manage 5 1 7477