This thesis considers a postal transportation planning problem in the transportation network of the form of hub and spoke. Given mail sorting centers and an exchange center, available vehicles and amount of mails to be transported between mail sorting centers, postal transportation planning is to make a transportation plan without violating various restrictions. The objective is to minimize the total transportation cost.
To solve the problem, a tabu search algorithm is proposed. The algorithm is composed of a route construction procedure and a route improvement procedure to improve a solution obtained by the route construction procedure using a tabu search. The tabu search uses the best-admissible strategy, BA, and the first-best-admissible strategy, FBA. The BA strategy selects the best admissible move from the current neighborhood which yields the greatest improvement or the least non-improvement in the objective function. The FBA strategy selects the first admissible move that provides an improvement in the objective value over the current solution; if all moves in the candidate list are tried without any improvement, then FBA selects the best recorded non-improving move.
The algorithm was tested on problems consisting of 11, 16 and 21 mail sorting centers including one exchange center. Solutions of the problems consisting of 11 mail sorting centers including one exchange center were compared with optimal solutions. On average, solutions using BA strategy were within 0.287% of the optimum and solutions using FBA strategy were within 0.508% of the optimum.
Computational results show that the proposed algorithm can solve practically sized problems within a reasonable time and the quality of the solution is acceptable.
