University of Twente Student Theses
Seed selection in multi-period planning with time windows
Bosch, A (2014) Seed selection in multi-period planning with time windows.
|
PDF
3MB |
| Abstract: | INTRODUCTION The planners using TRP pass four steps in generating a plan. Successively, the planners manually plan some difficult customers, TRP generates an initial solution with the sequential insertion algorithm, TRP improves this solution with the improvement steps, and the planners make some manually adjustments to the generated trips. Especially this last step cost the planners too much time at this moment. However, with these manual adjustments the planners are able not only to improve the visual attractiveness of the plan, but also the costs, number of kilometers driven, and the number of driving hours. The goal of the research is to “find the cause why the plan generated with TRP is visually less attractive than the plan after the manual adjustments of the planners and develop an improvement of the current planning algorithm used by TRP with a focus on improving the initial solution” CAUSE OF THE PROBLEM In this research, we used the customer Zeeman as leading example. We investigated the cause of the problem by analyzing the differences between the plan generated with the current algorithm of TRP and the plan that is manually adjusted by the planners of Zeeman. Two important characteristics of the planning, which make it difficult to generate a clustered and feasible plan, are the time windows of the orders and the required vehicle types for delivery of orders. We defined indicators that examine the quality of the plan and indicators that specifically judge the extent of clustering in a plan. The four indicators of the latter are: the number of cities that are visited by more vehicles than required, the average driven distance between the first and the last order in a trip, the average radius of the clusters, and the average capacity utilization of the vehicles. We found that on all indicators, the manually adjusted plan of Zeeman scores better than the plan generated by TRP’s original algorithm. We concluded that it was not possible to identify one single cause. The most plausible explanation is that the planners explore the neighborhood of the location of the order before inserting the order into a trip, where TRP does not consider this. CURRENT ALGORITHM OF TRP The current algorithm in TRP consists of two phases. In the first phase, TRP generates an initial solution. The initial solution is generated with the sequential insertion algorithm. This algorithm consists of four steps: 1. Select a vehicle 2. Select a seed order 3. Assign orders to the trip 4. Move the trip to a smaller vehicle In the second phase of TRP’s current algorithm, the initial solution is improved by performing several improvement steps based on local search. DEVELOPED APPROACHES When we analyzed the operating procedure of the sequential insertion algorithm in the provided cases, we concluded that we tackle the heart of the problem when we improve the second step: select the seed order. The most promising solution found in literature is the circle covering method of Savelsbergh (1990). We used this method as a basis for generating the clusters in the approaches we developed. We generate a cluster for each order and determine the radius of this cluster. Next, we defined two different methods to determine which seed order to use (sequential approach) or which cluster to merge (parallel approach). In the first method, we select the cluster with the smallest radius. In the second method, we select the cluster with the largest difference between the radii of different shifts. We call the selection criterion of the method the incentive. We developed two approaches. The first approach is a parallel approach. In the parallel approach, we simultaneously merge the two clusters with the highest incentive. We tested the approach with both the smallest radius and the largest difference incentive. The parallel approach shows multiple strong points on which the plan is improved. With both incentives, the visual attractiveness scores high; the solution looks more clustered. This is confirmed by the performance indicators. There are some trips with violations. The second approach is an adjustment to the sequential insertion algorithm. We developed two variants. In the first variant, we only change the seed selection step. We use the smallest radius of a cluster or the largest difference between the radii of different shifts as selection criterion. The variant with the smallest radius does not give a feasible solution; there are too many unplanned orders because the required vehicle was no longer available. With the largest difference incentive, we overcome this problem. We again used one of the incentives as selection criterion for the seed, but in the approach, this is the first step of the algorithm and we select the vehicle in the second step. CONCLUSION The parallel approach scores relatively high on clustering, but the costs are relatively high in comparison to the sequential approach. This is mainly caused by the additional number of vehicles the parallel approach needs to plan all orders. The largest difference incentive gave for both approaches a better result. In that method, we consider both the time windows of the orders and the vehicle preference of neighboring orders in our selection process for a seed order. We concluded that we succeed in improving the plan of TRP for the case of Zeeman. The two most promising approaches are the parallel approach with the smallest radius incentive and the sequential insertion algorithm with seed selection as first step. The sequential approach gives a better overall result, where the parallel approach gives better results with respect to clustering. It depends on the preference of the planners which method they prefer. Most planners will prefer to improve the visual attractiveness of the plan, which would plead for the sequential insertion algorithm with seed selection as first step and the largest difference incentive. |
| Item Type: | Essay (Master) |
| Faculty: | BMS: Behavioural, Management and Social Sciences |
| Subject: | 55 traffic technology, transport technology |
| Programme: | Industrial Engineering and Management MSc (60029) |
| Link to this item: | https://purl.utwente.nl/essays/64672 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page