Door-to-Door delivery in Iran - Local search (4)
On modeling door-to-door parcel delivery services in Iran
Since the solution space of the proposed model is complex, the output solution of the three consecutive SA may ignore some features of the final solution and need some improvement. A local search is considered for this amelioration in a way that the method check all routes to consider if it is possible to allocate all or part of a route to the second nearest hub or not. In this step, the algorithm only changes the places of assigned nodes and may violate the predetermined time window if it can amend the profit of the network.
Expand the allocated nodes
All before mentioned steps of the solution method attempt to improve the system profit by considering all nodes which can be covered in a predetermined time window (e.g. 24 hours) by at least one hub. In this step, the method considers all unassigned nodes to examine if it is economical to include them in the final delivery system. To do so, the algorithm can insert them to the current routes or open a new route for them. Although adding each node bring some money for the system and improve the profit, it may increase the number of routes or prolong the traveling distance of vehicles and increase the routing costs. Besides, a penalty cost is considered for all parcels of the routes which violate standard routing time (distance) to prevent low demand nodes to be imposed on the system.
The proposed method consists of sixth steps each of which should be repeated Nbest times to generate output solutions. The descriptive flowchart of the procedure is shown in Figure 2.
In this session, first, the proposed model and solution method are tested by the results of solving small test problems. The solution method is further tested by a case of all 31 capital cities of Iran provinces.
Fig. 2. Flowchart of the solution method
Comparing the model and solution method In order to validate and compare the proposed model and solution method, the model was coded in GAMS software to be solved with CPLEX solver and the solution method was coded in MATLAB software. The MIP model and solution method was run using Intel CoreI5, 3.1 GHz compiler with 8 GB of RAM, in a way that the CPLEX uses the parallel processing mode but the MATLAB program was run in the single processing mode.
The efficiency of meta-heuristics depends totally on the correct choosing of parameter values. Based on some preliminary tests on 20 node test problem, the values of the three parameters of three consecutive SA, named MaxIter, T0 and α, were selected by Taguchi method (Ross, 1989). Table 2 shows the results of tested parameters.
Table 2. Parameter settings of SAs by Taguchi method
Five different test problems similar to the actual problem with different size of 8, 10, 12, 15 and 20 nodes were considered, but the solver was able to solve only 8 nodes test problem in less than 1 hour, So five test problems with 8 nodes created and solved by the model and solution method. The results in Table 3 show the effectiveness of the proposed solution method in comparison with the model.
Table 3. The results of the model and the solution method on small test problems with 8 nodes
In this section, a case of road transportation in Iran is studied to validate the performance of the proposed solution method in real-world problems. The case corresponds to the road transportation network in Iran with 31 capital cities of Iran provinces. Since there is no reliable information about the travelling time between two cities of Iran, the distances between cities were taken into account. As the roads between large cities are relatively standard, by knowing the speed of vehicles, the distances can be easily transformed to the traveling time.
Vehicles in the routes or line haul connections may be faced with some conditions such as traffic before and after cities, mechanical breakdown, or even prolonged loading and unloading in origin or destinations nodes. As mentioned before, there are no stopovers in line hauls and all hubs are connected to each other via direct links, so the average speed of vehicles in line haul is considered 80 km/h. However, vehicles which travel in the routes should stop in some nodes for pickup or delivery of parcels, so the average speed of in routes is considered 70 km/h.
To simulate real conditions, the minimum and maximum distances in line haul connections are set on 320 and 1280 kilometers (which means 4 and 16 hours). But total available time for 24 hours of delivery is set on 23 hours with one hour of tolerance for unexpected conditions. Therefore, the maximum route time of vehicles can be calculated based on the selected hub nodes. For example, if the time/distance between selected hubs is 8 hours/640 kilometers, the remaining time is 15 hours which should be split in half for pickup and delivery route ways. Considering 70 km/h for the speed of vehicles in route transportation, the distance between hub and its last node cannot violate 7.5 h or 525 km.
To respect the confidentiality of the studied parcel delivery companies, all prices and costs normalized based on the price of delivering one parcel in the system. So the revenue of transporting each parcel is considered 1 monetary unit. The capacity of the vehicle is 2000 kg with the cost of 12 monetary units per hours for the routes and 10 monetary units per hours for line haul connections. The expense of running each route is considered 50 monetary units and the amount of demand between cities is set based on the average demand of the analyzed companies. Finally, a penalty cost of 0.2 is considered for all collected and delivered parcels of each route that violate 24 hours of delivery in step 6 of the solution method.
The case was solved 20 times (Nbest=20) with three different hub numbers with and without penalty costs. In Table 4 the best result of solving the case with the proposed solution method is illustrated.
Table 4. The best result of the Iran case with 31 cities
In both cases of with and without penalty cost, the best profit is achieved with three hubs. The result shows that step 6 has the most important effect on the system profit when there is no penalty cost, but with penalty cost, the last step has actually no impact on the final results. Step 4 has a great impact on the network profit when managers have financial sources of only one hub.
Analyzing the effect of the different steps of the method, the best founded solution of steps 4, 5, and 6 in solving the case with three hubs and without penalty cost are illustrated in Figure 3, 4 and 5, respectively. It is obvious that each step has great potential on the improvement of the final result. In the proposed solution, two big cities of Tehran and Esfahan along with the Hamedan has selected as hubs. The longest distance between these cities are 464 kilometers which mean approximately 6 hours of traveling. So, based on the mentioned assumptions, the longest distance of routes between a hub and its last node should be less than 7.5 hours or approximately 600 kilometers. Recall that this rule should be considered in the first four steps, while in step 5, the method can violate the normal time window and change the route but cannot add new route to the network, and in step 6, the method cannot change the current route but can add new nodes to the network by violating normal time window. As shown in Figure 3, the distances of two nodes of 2 (Ardabil) and 11 (Tabriz) from the hub node 12 (Tehran) are 591 and 599, respectively and each of them is separately connected to their hub; however, in step 5, this two cities are joined together and composed a route to increase the profit of the network. Other changes can be found by comparing Figures 3 and 4.
In step 6, as there is no penalty cost for delays, the method added five new cities to the network and the final profit has improved by more than 15%. Although the method added some new cities and is covered five new cities, three cities cannot cover by the system yet. The reason is related to their small demands, so the cost of pickup and delivery of them is absolutely more than the profit that can be earned by covering them
Fig. 3. Parcel delivery network after three consecutive SA
Fig. 4. Parcel delivery network after local search
Fig. 5. Final parcel delivery network
Conclusion and further research
Logistic service providers, especially parcel deliveries, confront very complicated situations in real case problems. Modeling a parcel delivery network, two different areas of hub location and vehicle routing should be integrated to model the network. Considering two door-to-door service providers of Iran, in this paper, a new MIP model with a new sixth-steps solution method based on the SA algorithm and local searches was presented. The purpose of the model was to maximize the profit of running a parcel delivery system in a sparse and wide country like Iran to find the number and place of the hubs, allocate nodes (i.e., cities) to hubs, and determine the routes connecting nodes to hubs. Proposed model and the solution method were evaluated based on the results of some small test problems. Also a real case of all 31 capital cities of Iran provinces was considered for further research with and without penalty costs. Furthermore, with numerical examples and figures, the effect of each step was shown on final solution. The results demonstrated that in the ideal form, the network should consist of three hubs in Tehran, Esfahan and Hamedan. With penalty costs, the network cannot cover eight cities; however, without penalty costs, the network can cover 28 cities. Since the proposed location-routing model is almost new, interested researchers can further expand the model to consider other objectives, such as maximizing covered cities or service quality. In this research, the company could only hire one kind of vehicle; a way to expand the proposed model is to consider vehicles with different capacities. Finally, some deterministic parameters, such as demands or travel time between two nodes, can be set as stochastic or fuzzy parameters to carefully model real cases.
Ref: Farzad Bahrami, Hossein Safari, Reza Tavakkoli-Moghaddam, Mohammad Modarres Yazdi - Iranian Journal of Management Studies (IJMS) - Vol. 9, No. 4, Autumn 2016- pp. 883-906