Door-to-Door delivery in Iran - Problem (3)
On modeling door-to-door parcel delivery services in Iran
Problem description and formulation
In this section, the problem is first described and formulated as a MINLP model and then linearize to an MIP form.
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.
Before presenting the formulation of the model, the indices and parameters of the model can be defined as follows:
Also, decision variables can be stated as below:
Now the proposed model is as follows:
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.
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 Černý (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 T0, 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 (α). 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.
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