Kalcsics, Joerg

Garcia Quiles, Sergio

Phusingha, Saranthorn

2021-08-04T16:43:29Z

2021-08-04T16:43:29Z

2021-07-31

In the sales districting problem, we are given a set of customers and a set of salesmen in some area. The salesmen have to provide services at the customers' locations to satisfy their requirements. The task is to allocate each customer to one salesman, which partitions the set of customers into subsets, called districts. Each district is expected to have approximately equal workload and travel time for each salesman to promote fairness among them. Also, the districts should be geographically compact since they are more likely to reduce unnecessary travel time, which is desirable for economic reasons. Moreover, each customer can require recurring services with different visiting frequencies such as every week or two weeks during a planning horizon. This problem is called the `Multi-Period Sales Districting Problem (MPSDP)' and can be found typically in regular engineering maintenance and sales promotion. In addition to determining the sales districts, we also want to get valid weekly visiting schedules for the salesmen corresponding to the customers' visiting requirements. The schedules should result in weekly districts with the following desirable characteristics: each weekly district should be balanced in weekly workload and geographically compact. The compactness in the schedules provides benefits when a salesman has to deal with short-term requests from customers or change a visiting plan during the week. Namely, the salesman can postpone a visit to another day if necessary, without increasing the travel time too much compared to the original schedule. This is beneficial when the salesman has to deal with unexpected situations, for example, road maintenance, traffic jams, or short notice of time windows from customers. Although the problem is very practical, it has been studied only recently. Since most of the previous literature on general scheduling problems did not consider compactness, a few recent studies have begun to focus on solving the scheduling part of the problem. The purpose of this research is to develop a more sophisticated exact solution approach as well as an efficient high-quality heuristic to solve the scheduling part. Eventually, with an effective elaborate method to solve the scheduling part, we aim for a robust algorithm to solve the districting and scheduling part of the problem simultaneously. This thesis contains three main parts. The first part introduces the problem and provides a mixed-integer linear programming formulation for only the scheduling part and formulation for the whole problem. The second part presents solution approaches, including an exact method and a heuristic, for only the scheduling part. The last part is dedicated to further development of a successful approach from the second part to solve the districting and scheduling part of the problem simultaneously. For solving the scheduling part, Benders' decomposition is developed as a new exact solution method. The linear relaxation of the problem is strengthened by adding several Benders' cuts derived from fractional solutions at the beginning of the algorithm. Moreover, a good-quality integer solution derived from a location-allocation heuristic is used to generate cuts beforehand, which significantly improves the upper bound of the objective function value. Nondominated optimality cuts are implemented to guarantee the strongest Benders' cuts in each iteration. Also, instead of generating a Benders' cut per iteration, we exploit the decomposable structure of the problem formulation to generate multiple cuts per iteration, resulting in a noticeable improvement in the lower bound of the objective function value. In the classical Benders' decomposition, one of the main factors that slow down the algorithm is that one has to solve the integer programmes from scratch in each iteration. To alleviate this problem, a modern implementation creates only one branch-and-bound tree and adds Benders' cuts derived from a solution in each node in a solution cut pool. This method is called branch-and-Benders' cut. To assess the suitability of the algorithm, we compare its performance on small data instances that contain 30$-$50 customers to the Benders' algorithm in CPLEX and show that our algorithm is highly competitive. Since an exact solution method usually struggles to solve realistic large data instances, a meta-heuristic called tabu search is proposed. A high-quality initial solution to start the algorithm is derived from the location-allocation heuristic. Three different neighbourhoods based on information about week centres or customers' week patterns are created within which we search for the best solution. An infeasible solution is allowed in the search to expand the search space. During the search, the size of a whole neighbourhood can be excessively large, so we limit the search to promising areas of the solution space to save computational time. Also, a surrogate objective value is used to save on computational time in cases when computing the real objective value is too time-consuming. Although the tabu search defines a list of forbidden moves to avoid the cycle of solutions, the algorithm can still struggle to avoid being trapped around a local optimum. Therefore, a diversification scheme is proposed for such cases. The algorithm is also accelerated by combining all neighbourhoods and selecting the appropriate neighbourhood for each iteration by a roulette wheel selection. It shows impressive results in small data instances that contain 30$-$50 customers. The comparison with built-in heuristics in CPLEX confirms the robustness of the tabu search algorithm. Finally, we combine the tabu search algorithm with our developed Benders' decomposition. Numerical results show that the tabu search method improves the upper bound of the Benders' decomposition algorithm. However, the overall performance is not satisfying so the combination of these two techniques still requires more proper development. As the tabu search algorithm performs well on the scheduling part, it is extended to solve the whole problem, i.e., the districting and scheduling part at the same time. Computational results on large data instances, which contain between 100 and 300 customers, demonstrate its capacity to derive a high-quality solution within a reasonable amount of time, i.e., less than 17 minutes. At the same time, the Benders' decomposition algorithm in CPLEX, which is a benchmark in this case, and the built-in heuristics in CPLEX cannot even find any feasible integer solution for most of the instances within an hour. Importantly, there is a conflict between the districting part and the scheduling part so we recommend solving both parts simultaneously for tackling the MPSDP. The multi-period sales districting problem is highly practical and challenging to solve. To the best of our knowledge, we are the first to propose a single integrated solution approach to solve the whole problem. Further studies including adding more realistic planning requirements into consideration and effective solution approaches to solve the problem are still required.

https://hdl.handle.net/1842/37866

http://dx.doi.org/10.7488/era/1142

en

The University of Edinburgh

Mixed integer linear programming

sales districting problem

multi-period

tabu search

Benders' decomposition

Multi-period sales districting problem

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy