We approached this question by using the concept of “cone-shape distribution function” which provides the optimal navigation of the spatial distribution of orders. We assumed that the lowest mileage for any truck can be determined with deployment of all available trucks. Hence, with centre as (0,0), the plane is divided into segments via equal radian, where the number of segments obtained are equal to the number of trucks available [Figure 1]. Figure 1 For every order, we obtain the segment number that it is allocated to and append it into a list of order of the particular segment. The perform_once function is called once and returns a list of segment lists. Next, within each segment, the Greedy algorithm is used to obtain an initial truck path by choosing the next nearest order starting from (0,0). If there is only one available truck, the 2-opt algorithm is used directly to ensure optimisation within the segment by swapping two order points in every possible combination until the shortest total distance of the segment has been achieved. If there are two or more available trucks, route optimisation between segments is considered via the array_opt function which swaps the nearest order point between adjacent paths. New greedy paths are then generated in the segments where the point is removed from and added to. If the maximum total distances of both paths are now lower, the new paths are implemented. Points will continue to be swapped until there are no further improvements. To balance the distance traveled by each truck as much as possible, the function iterates through all segments bi-directionally and array_opt is called twice - clockwise and anti-clockwise. This same path is then looped through the entire process described earlier for five times to ensure stabilisation of output results. With the optimal routes of the trucks, it is appended into a list which completes the scheduling of the trucks.
Get Free Quote!
345 Experts Online