Printer Friendly

On modeling door-to-door parcel delivery services in Iran.

Introduction

A parcel delivery service provides an inexpensive network to transfer parcels between cities (nodes) each of which as a center may send or receive parcels. Since it is not economical to link all nodes of a network to each other, service provider links covered nodes by setting one or more hubs. Hubs are facilities that work as consolidation, connecting, and switching point for flow between local centers (Zanjirani-Farahani et al., 2013). Centers (non-hub nodes) are connected to their nearest hub node through some routes by a truck or larger vehicles. Vehicles collect/distribute all parcels of the non-hub nodes located in their routes and provide links between non-hub nodes and the nearest hub node. As all centers cannot supply a truckload demand, Less-Than-Truckload (LTL) transportation strategy may help to achieve economies of scale in parcel delivery companies (Wasner & Zapfel, 2004).

To model a parcel delivery system, two different subjects of hub location and vehicle routing problems should be considered. Although the former is a strategic decision and the later is an operational one, researchers believe that these two decisions are strongly linked (Salhi & Rand, 1989) and only the integrated model can provide a reasonable solution for such a complex situation. Furthermore, parcel delivery models have some common features such as: (I) all hubs are connected to each other, (II) nodes are connected to at least one hub, or (III) nodes are connected to the hubs through some tours. However, modeling parcel delivery in each region totally depends on the local features which contravene global standards.

This paper is supposed to examine parcel delivery services and to model the current design of parcel providers of Iran. Although door-to-door parcel delivery has more than 50 years of service record in Iran, it is still an incomplete logistic service and is not able to provide a smooth and steady service for all cities of the country. There are two important reasons for this happening: Iran geographical conditions and imbalance demands of cities. Iran is the 18th-largest countries of the word with the rugged mountain ranges in the west, wide desert basins in the east and long shores in the north and south. So, while the east part contains sparse cities and restricted roads, the other part of the country is more crowded with close cities and complete roads. Besides, not having proper investment in the east part of the country, in addition to the other reasons, causes imbalance demands between east and other part of the country.

To prepare enough information for investigation, some interviews were conducted with managers of two pioneer parcel providers in Iran and their systems were precisely observed for three months. So, the result can be appropriately generalized for other service providers of Iran. It should be mentioned that most passengers' transportation companies also provide parcel delivery services between cities which have transportation line and some of them with extra charges are even provided door-to-door service. But these companies are not included in this study.

Almost all parcel providers have a hub in Tehran, the most populated and capital city of Iran, while only some providers have more than one hub. Hubs are connected to each other while nodes connect to hubs in stopover routes (as mentioned by Kara & Tansel, 2001); it means that there is no tour between a hub and its allocated nodes. Companies provide delivery services to the cities (branches) in which have some agents. Agents pick up parcels from customer's places or customer can deliver his/her parcel to the nearest agent place. Each agent delivers its parcels to its city branch in the predetermined time windows. If the parcel amount of a branch is as much as a vehicle capacity, it directly transfer to the nearest hub, otherwise, a vehicle, which may collect the parcels of some near branches, will come to pick up the parcels and transfer them to the hub. All collected parcels will be sorted, consolidated, and allocated to some routine routes. Vehicles leave the hub to distribute the parcels of some distinct branches which located in the route. Delivery and pickup is not simultaneous, so when vehicles reach to the last branch (city), stay for a while (depending on the route between one hour to one day) and then return to the hub while pick up the collected parcels of the visited branches. In fact, each branch is allocated to a hub which is responsible to serve it through a specific route. It means hubs only handle the parcels related to the branches of their routes and transfer all other parcels to the responsible hubs through line haul connections (hub to hub connections).

Delivery time totally depends on the network and which differs from 24 to 72 hours. In all companies, delivery time between non-hub nodes to the hubs and vice versa is less than 24 hours, as agents call them one way route parcels. However, the delivery time between two non-hub nodes depends only on the place of nodes, and their routes.

As collecting/distributing parcel inside the cities is done by agents and selecting the routes is totally depends on their experience; it is not the parcel provider concern and only two levels of hub-nodes (routes) and hub-hub (line-haul) connections will be considered in this investigation. Therefore, parcel provider managers are interested in answering the following questions by scientific investigation:

* Where the hubs should be opened to increase the profit of the parcel service?

* Which cities should be considered in the final network and covering which cities is not economical?

* How many routes should be opened for each hub, and what is the best way to allocate branches (cities) to the routes?

* How many vehicles are needed to handle the delivery part of the network system?

The rest of the paper is organized as follows: The next section reviews the related literature. In Section 3 the problem definition and formulation is described in details. Proposed method based on simulated annealing algorithm is explained in Section 4. Experimental results on some small test problems and on a case of Iran road network are presented in Section 5. Last Section discusses the summary and conclusions of the proposed model and solution method.

Literature review

To model a parcel delivery service, two different areas of hub location and vehicle routing problem were integrated as hub location-routing problem (Wasner & Zapfel, 2004). Aggregating two areas of location and routing appeared by the study of Laporte (1988), which named it location-routing problem (LRP). LPRs typically present answers for three different questions of managers: the number and location of facilities, the allocation of nodes to the facilities, and design of the routes through allocated nodes of the facility (Lopes et al., 2013). The facility can be a hub which works as consolidation, connecting, and switching point between origins and destinations that send their parcels as bundles to achieve economies of scale (Zanjirani-Farahani et al., 2013).

The first mathematical formulation and solution method for hub location problem was developed by O'Kelly (1986a, 1986b). Campbell (1994) presented several classical location problems in hub location problem format. Ernst and Krishnamoorthy (1996) formulated hub location of Australian Post as a new linear integer programming model. They introduced a solution method based simulated annealing which was able to solve large problem with 200 nodes and 10 hubs. Bruns et al. (2000) proposed a discrete location model for restructuring Swiss parcel delivery services to improve competitiveness of the Swiss Post.

Considering parcel delivery services of Turkey, Kara and Tansel (2001) proposed the problem of last arrival hub location problem in which unavoidable waiting times can occur at hubs because of lack of synchronization of arriving and departing vehicles. In their work, each hub could handle pickup and delivery of some nodes through paths in which vehicles does not end at the departure point of hubs. Although they did not mentioned to routing part, their study was similar to hub location-routing; LRP is broad enough to include all types of vehicle distribution considerations, either routes or paths (Lopes et al., 2013).

Wasner and Zapfel (2004) considered a parcel delivery problem and proposed a model for Austria postal system. In their model, vehicles perform both deliveries and pickups, and all inter-hub flows are carried out by a central hub. The problem was defined as to determine the location of depots and hubs, to allocate the customers and postal zones to service areas, and to establish the delivery routes. The authors presented mixed-integer nonlinear programming (MINLP) formulation and a hierarchal heuristic algorithm to solve the problem. Tan and Kara (2007) determined the constraints, requirements and criteria of the hub location problem especially for cargo delivery problems. They present integer programming formulations and large-scale implementations of the models within Turkey. Yaman et al. (2007) concentrated on the service structure of cargo delivery companies and proposed a minimax model that focuses on the minimization of the arrival time of the last item. They introduced a new variant of last arrival hub location problem which allows multiple stopovers for the delivery firms of Turkey. Comprehensive reviews of the location-routing models and their applications are provided by Laporte (1988), Min et al. (1998), Nagy and Salhi (2007), and Lopes et al. (2013).

Recently, Karaoglan et al. (2012) proposed two polynomial MixedInteger Linear Programming (MILP) formulations for the LRP with simultaneous pickup and delivery. The first formulation was a node-base, while the second one was a flow-based. They proposed a two-phase heuristic algorithm based on simulated annealing to solve the large-sized problems, and two initialization heuristics to generate an initial solution. Cupic and Teodorovic (2014) presented a multi-objective approach for solving a parcel delivery hub location problem. They considered two conflict objectives of maximizing profit and maximizing service level and solved the model based on compromise programming and genetic algorithm and implemented the method on a relatively small network with 16 nodes in Serbia. Estrada-Romeu and Robuste (2015) considered hub location problem with stopover to identify if consolidation strategies were cost-efficient in less-than-truckload systems similar to parcel delivery services. They took spatial distribution of shipment loads among centers into account for the proximity criterion. The output showed that the proposed methodology might reduce up to 20% the transportation costs. In Table 1 related literature is briefly overviewed.

Problem description and formulation

In this section, the problem is first described and formulated as an MINLP model and then linearize to an MIP form.

Problem description

In parcel delivery systems, the most important goal is to increase the profit of the running the delivery system. Managers need to pursue common practice of 24 and 48 hours of delivery to satisfy the customers, so they may decide not to cover all nodes of the network. Depending on the budget, the number of hubs will be determined by decision makers but all hubs are connected to each other and all covered nodes are connected to only one hub through a route. Considering some expenses, each route starts from and ends to a hub in the form of a path; so, more than one route can start from a hub. Each vehicle in the routes, first deliver all parcels of its allocated nodes and then pick up the parcels of the visited nodes. The number of vehicles in each path route or line haul depends on the maximum number of bundled parcels in one way of the route. The capacity of each vehicle is limited but the company can hourly rent as many vehicles as needed. Depending on the place of the hubs, managers are eager to cover all cities in the range of 24 hours of delivery but other cities are covered only when adding them increase the profit.

Problem formulation

Before presenting the formulation of the model, the indices and parameters of the model can be defined as follows:
N =         Set of nodes
{1,2,...}
i,j         Index of nodes, i ,i [member of] N
k           Index of routes
n           Index of the place of nodes in routes
m, m'       Index of hubs,
[W.sub.ij]  Number of parcels that would be transferred from node i to j
[T.sub.ij]  Road time between nodes and (where, [T.sub.ij] = [T.sub.ji])
[T.sub.1]   Maximum time that vehicles allow to travel through a route
            in 24 hours
[T.sub.2]   Maximum time that vehicles allow to travel through a route
            in 48 hours
TH          Maximum time that vehicles allow to travel between two hubs
CR          Fixed cost of establishing a route
CK          Variable cost of renting vehicles in routes (per kilometer)
CH          Variable cost of renting vehicles between hubs
            (per kilometer)
CA          Maximum capacity of vehicles
S           Selling price of each parcel
F           Fine per each parcel located in the route used
NH          Number of hubs which should be located in the network


Also, decision variables can be stated as below:
Z             Objective function

[x.sub.im]    [mathematical expression not reproducible]
[y.sub.nik]   [mathematical expression not reproducible]
[b.sub.ij]    [mathematical expression not reproducible]
[VR.sub.k]    Number of needed vehicles in route k
[VH.sub.mm']  Number of needed vehicles between two hubs m and m'
[TR.sub.k]    Needed time for collecting and delivering parcels in route
              k
[PC.sub.k]    Amount of the collected parcels in route k
[PD.sub.k]    Amount of the delivered parcels in route k
[PM.sub.k]    Maximum amount of transferred parcels in route k
[PH.sub.mm']  Amount of the transferred parcels between hub m and


Now the proposed model is as follows

(1)

s.t.

[mathematical expression not reproducible] (2)

[mathematical expression not reproducible] (3)

[mathematical expression not reproducible] (4)

[mathematical expression not reproducible] (5)

[mathematical expression not reproducible] (6)

[summation over m][x.sub.mm]=NH (7)

[mathematical expression not reproducible] (8)

[mathematical expression not reproducible] (9)

[mathematical expression not reproducible] (10)

[mathematical expression not reproducible] (11)

[mathematical expression not reproducible] (12)

[mathematical expression not reproducible] (13)

[mathematical expression not reproducible] (14)

[mathematical expression not reproducible] (15)

[mathematical expression not reproducible] (16)

[mathematical expression not reproducible] (17)

[mathematical expression not reproducible] (18)

[mathematical expression not reproducible] (19)

[mathematical expression not reproducible] (20)

[mathematical expression not reproducible] (21)

[mathematical expression not reproducible] (22)

[mathematical expression not reproducible] (23)

[mathematical expression not reproducible] (24)

Analyzing the objective function of the parcel delivery system (1), it consists of the earned profit from the delivered parcels of the covered nodes minus the transportation costs of routes and line hauls, the costs of opening new routes, and penalty costs of violated routes. Constraint (2) enforces the model to count the route place of nodes in a numerical order. Constraints (3) limit each non-hub node to be allocated to only one place of one route. As the system is not forced to cover all nodes, Constraint (4) limits each node of a route to take at most one place of a route and Constraint (5) expresses that each node at most dedicate to one hub. Constraint (6) shows that each node dedicated to another node as a hub only when it is selected as a hub and in (7) the number of hubs is determined. In (8) the model ensures that the first node of each route works as a hub. Other Constraints of (9) - (11) check out that other nodes in each place of routes allocate to the right hubs.

Relation (12) define the needed time for collecting and delivering parcels in route k. Constraint (13) shows the time window restriction from node i to j. Relations (14) and (15) are related to the pickup and delivery of parcels in each route, respectively. Relation (16) demonstrates that only the maximum amount of pickup and delivery should be considered in each route. Relation (17) shows the amount of parcels in line haul connections. Based on the capacity of vehicles, the optimal number of vehicles in each route and line haul can be settled by constraint (18) and (19). Ultimately, constraints (20)-(24) determine the type of each decision variable.

Although the proposed model in this form is non-linear mixed integer programming, multiplying of two decision variable in objective function and Constraint (13) and maximum variable in constraint (16) can easily be transformed to linear ones (Wolsey, 1998). So, the model transform to the mixed integer programming model which can be solved optimally in small size test problems.

Solution method

The proposed model is NP-hard and exact methods cannot solve the problem in a reasonable time periods even for small test problems (e.g., with 10 nodes). To solve the model, a new multi-steps method based on Simulated Annealing (SA) is proposed. In the following, firstly, generating initial solutions is described, and then SA algorithm is expressed in flowchart form. Local search and the approach are discussed in details afterwards. Finally, the proposed method is described in algorithmic form of a flowchart in the last part of this session.

Generating initial solutions

Each solution of the model consists of hub locations, allocated nodes to each hub, and routing of the allocated nodes to the hubs. As the model tries to maximize the system profit, it is able to cover only part of nodes. Setting the number of needed hubs (Nhub) by service providers, Nhub nodes are randomly selected regarding limitations of minimum and maximum distance between hubs. Based on the selected hubs, other non-hub nodes, in the range of 24 hours of service, are allocated to the nearest hubs. Since there are numerous possible paths routing for each selected hub, routing of allocated nodes is generated based on the flowing scheme:

Repeat the procedure until all allocated nodes assigned to a route: Open a new route. Set current distance to zero. Label the hub as the first node of the new route and as the current node of the route. Calculate the distance between the current node and all unassigned nodes. Choose the node related to the shortest distance and label it as the next node of the route and as the current node. Update the current distance by adding distance between current node and selected node to the current distance. Repeat the procedure until distances between the current node and other nodes plus current distance violates distance limitations. Close the route.

Three consecutive SA

SA is a probabilistic technique proposed by Krikpatrick et al. (1983) and Cerny (1985) independently to find or approximate the global optimum of a given function. It emulates the physical process of a hot solid, which is slowly cooled to reach structure of a frozen one. The algorithm starts with a current solution and an initial temperature [T.sub.0], set to a high value. In each temperature, the algorithm iterate up to a predetermined number of iteration and then the temperature decrease by a parameter (a). Based on the neighborhood structure and current temperature, a new solution is randomly generated in each iterations to improve the current solution. If the new solution is better than the best solution ever found, it substitutes the best and current solution, but if the new solution is not as good as the best solution, a number is generated randomly in the range of [0, 1] and compared with an appropriate function (e.g. Fig. 1). If the random number was smaller than the function, the new solution substitutes the current solution. Accepting worse solutions is a fundamental property of this method and allows for a more extensive search towards the optimal solution. The algorithm continues until encounter the predetermined minimum temperature. Figure 1 illustrates the flowchart of the SA algorithm.

As mentioned before, each solution of the proposed model consists of three different parts of hub locations, node allocation, and routing of the allocated nodes to the hubs. In the proposed solution method three consecutive SA is utilized to handle these parts.

In the first SA, the goal is to improve hub location; each time one non-hub node is randomly selected and substitutes by one hub node. If new hub rests between the minimum and maximum distances of hubs limitation, the new combination forms a new solution. To calculate the profit of the new solution, node clustering is determined based on the nearest distance but routing is fixed based on the routing explained in previous session.

The aim of the second SA is to improve the clustering of the non-hub nodes. In this step, the algorithm attempts to change the allocation of nodes to hubs without changing hub location. To do so, one allocated non-hub nodes is selected and randomly assigned to another hub, if possible. Similar to the previous step, the routing is fixed in order to calculate the profit of the new solution.

Third SA dedicated to improve routing of previous solution. In this step, hub location and node clustering is fixed and a node is randomly removed from its current route and assigned to another route, if possible.

Local search

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.

Proposed approach

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.

Experimental results

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.

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, [T.sub.0] and a, were selected by Taguchi method (Ross, 1989). Table 2 shows the results of tested parameters.

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.

Case study

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.

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.

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.

References

Bruns, A., Klose, A., & Stahly, P. (2000). Restructuring of Swiss parcel delivery services. OR Spectrum, 22(2), 285-302.

Campbell, J. F. (1994). Integer programming formulations of discrete hub location problems. European Journal of Operational Research, 72(2), 387-405.

Cerny, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of optimization theory and applications, 45(1), 41-51.

Cupic, A., & Teodorovic, D. (2014). A multi-objective approach to the parcel express service delivery problem. Journal of Advanced Transportation, 48(7), 701-720.

Ernst, A. T., & Krishnamoorthy, M. (1996). Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location science, 4(3), 139-154.

Estrada-Romeu, M., & Robuste, F. (2015). Stopover and hub-and-spoke shipment strategies in less-than-truckload carriers. Transportation Research Part E: Logistics and Transportation Review, 76, 108-121.

Kara, B. Y., & Tansel, B. C. (2001). The latest arrival hub location problem. Management Science, 47(10), 1408-1420.

Karaoglan, I., Altiparmak, F., Kara, I., & Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4), 465-477.

Krikpatrick, S., Gelatt Jr. C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.

Laporte, G. (1988). In: Golden GI. Assad A.A., editors. Location-routing problems. In vehicle routing: Methods and studies (pp. 163-198). Amsterdam: North-Holland.

Lopes, R. B., Ferreira, C., Santos, B. S., & Barreto, S. (2013). A taxonomical analysis, current methods and objectives on location-routing problems. International Transactions in Operational Research, 20(6), 795-822.

Min, H., Jayaraman, V., & Srivastava, R. (1998). Combined location-routing problems: A synthesis and future research directions. European Journal of Operational Research, 108(1), 1-15.

Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2), 649-672.

O'kelly, M. E. (1986a). The location of interacting hub facilities. Transportation Science, 20(2), 92-106.

O'Kelly, M. E. (1986b). Activity levels at hub facilities in interacting networks. Geographical Analysis, 18(4), 343-356.

Ross, R.J. (1989). Taguchi techniques for quality engineering. New York: McGraw-Hill.

Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 39(2), 150-156.

Tan, P. Z., & Kara, B. Y. (2007). A hub covering model for cargo delivery systems. Networks, 49(1), 28-39.

Wasner, M., & Zapfel, G. (2004). An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics, 90(3), 403-419.

Wolsey, L.A. (1998). Integer programming (Vol. 42). New York: Wiley.

Yaman, H., Kara, B. Y., & Tansel, B. C. (2007). The latest arrival hub location problem for cargo delivery systems with stopovers. Transportation Research Part B: Methodological, 41(8), 906-919.

Zanjirani-Farahani, R., Hekmatfar, M., Arabani, A. B., & Nikbakhsh, E. (2013). Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, 64(4), 1096-1109.

Farzad Bahrami (1), Hossein Safari (1)*, Reza Tavakkoli-Moghaddam (2), Mohammad Modarres Yazdi (3)

1. Faculty of Management, University of Tehran, Tehran, Iran 2. School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran & LCFC, Arts et Metier Paris Tech, Metz, France 3. Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

(Received: June 12, 2016; Revised: November 12, 2016; Accepted: November 16, 2016)

(*) Corresponding Author, Email: hsafari@ut.ac.ir
Table 1. Related literature

Researcher         Year   Title                       Case

O'Kelly            1986   The location of             25 cities of
                          interacting hub             USA
                          facilities
Campbell           1994   Integer                     -
                          programming
                          formulations of
                          discrete hub location
                          problems
Ernst &            1996   Efficient algorithms        Australian
Krishnamoorthy            for the uncapacitated       Post
                          single allocation p-
                          hub median problem
Bruns et al.       2000   Restructuring of            Swiss Post
                          Swiss parcel
                          delivery services
Kara & Tansel      2001   The latest arrival          -
                          hub location
                          problem
Wasner &           2004   An integrated multi-depot   Austria
Zapfel                    hub-location                postal
                          vehicle routing             system
                          model for network
                          planning of parcel
                          service
Tan & Kara         2007   A hub covering              Cargo
                          model for cargo             delivery
                          delivery systems            firms of
                                                      Turkey
Yaman et al.       2007   The latest arrival          Cargo
                          hub location                Delivery
                          problem for cargo           firms of
                          delivery systems            Turkey
                          with stopovers
Karaoglan et al.   2012   The location-routing        -
                          problem with
                          simultaneous pickup
                          and delivery:
                          Formulations and a
                          heuristic approach
Cupic &            2014   A multi-objective           A parcel
Teodorovic                approach to the             Delivery
                          parcel express              Service of
                          service delivery            Serbia
                          problem

Researcher         Brief explanation

O'Kelly            Presenting the first mathematical formulation and
                   solution method for hub location problem
Campbell           Proposing several classical location problems in hub
                   location problem format
Ernst &            Formulating hub location of Australian Post as a new
Krishnamoorthy     linear integer programming model.
                   Introducing a solution method based simulated
                   annealing to solve large problem
Bruns et al.       Proposing a discrete location model for restructuring
                   Swiss parcel delivery services
Kara & Tansel      Presenting the problem of last arrival hub location
                   problem in which unavoidable waiting times can occur
                   at hubs because of lack of synchronization of
                   arriving and departing vehicles.
Wasner &           Proposing a model for Austria postal system to
Zapfel             determine the location of depots and hubs, to
                   allocate the customers and postal zones to service
                   areas, and to establish the delivery routes
Tan & Kara         Determining the constraints, requirements and
                   criteria of the hub location problem especially for
                   cargo delivery problems.
                   Presenting integer programming formulations for
                   solving large-scale models within Turkey introducing
Yaman et al.       a new variant of last arrival hub location problem
                   which allows multiple stopovers for the delivery
                   firms of Turkey
Karaoglan et al.   Presenting two polynomial Mixed-Integer Linear
                   Programming formulations for the LRP with
                   simultaneous pickup and delivery.
                   Proposing a two-phase heuristic algorithm based on
                   simulated annealing to solve the large-sized
                   problems.
Cupic &            Presenting a multi-objective approach for solving a
Teodorovic         parcel delivery hub location problem.
                   Implementing the method on a relatively small network
                   with 16 nodes in Serbia

Table 2. Parameter settings of SAs by Taguchi method

First SA               Second SA              Third SA
Parameter   Selected   Parameter   Selected   Parameter   Selected
            value                  value                  value

MaxIter     30         MaxIter     30         MaxIter     30
            10         [T.sub.0]   12         [T.sub.0]   10
[alpha]      0.995     [alpha]      0.96      [alpha]      0.99

Table 3. The results of the model and the solution method on small test
problems with 8 nodes

Problem            CPLEX      Solution Method
          Z        CPU Time   Z                 CPU Time

1         832.5    1245.94    832.5             32.34
2         670.9    1500.58    670.9             27.12
3         789.1    3600.00    789.1             22.56
4        1203.7    2450.02   1203.7             41.93
5         912.2     320.98    912.2             26.82

Table 4. The best result of the Iran case with 31 cities

                      Without Penalty                With Penalty
Best profit           Nhub=1   Nhub=2    Nhub=3      Nhub=1     Nhub=2
of steps

Step 1: Initial       4614.2    4685     5098.5      4232.7      5296.9
Step 2: First SA      4639.6    7599.7   7979        4639.6      7599.7
Step 3: Second SA     4639.6   77033     8206.8      4639.6     77033
Step 4: Third SA      6384.4    8251.5      8.377.5  6384.4      8177.4
Step 5: Local Search  6384.4    8368.4   8575.7      6384.4      8368.4
Step 6: Expand        6384.4    9662.4   9728.4      6384.4      8368.4
network
CPU Time               112.2     116.5    129.6       117.7       123.4
                      (sec)

                      With Penalty
Best profit           Nhub=3
of steps

Step 1: Initial       5326.3
Step 2: First SA      7979
Step 3: Second SA     8206.8
Step 4: Third SA      8344.5
Step 5: Local Search  8575.7
Step 6: Expand        8575.7
network
CPU Time               125.3
COPYRIGHT 2016 University of Tehran, Farabi College
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Bahrami, Farzad; Safari, Hossein; Tavakkoli-Moghaddam, Reza; Yazdi, Mohammad Modarres
Publication:Iranian Journal of Management Studies
Article Type:Report
Geographic Code:7IRAN
Date:Sep 22, 2016
Words:6395
Previous Article:The impact of technological innovation capabilities on competitive performance of Iranian ICT firms.
Next Article:A New Robust Bootstrap Algorithm for the Assessment of Common Set of Weights in Performance Analysis.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters