수익을 최대로 하는 픽업 및 배송문제의 세분화 타부서치 알고리즘 기법 연구

In this paper, we propose the granular tabu search heuristic for the pickup and delivery problem to maximize the total revenue by transportation of customer demands with a limited fleet of vehicles. The problem, denoted as the pickup and delivery maximum covering problem, is designed for the efficient operation of military air transportation system, it also can be applied to the competitive door-to-door transportation systems. In the problem, there exist several transportation requests, each of which consists of demand volume, price value, and unique pickup and delivery locations. The company maximizes the sum of the price value from allocated customers under the vehicle capacity and the maximum route length constraints. Since the suggested mathematical formulation is too hard to solve within the reasonable computational time, the local search heuristic algorithm is suggested. The algorithm contains two procedures for the efficient search of neighbor solutions, and the first suggestion is the granularity condition that only considers the edges with smaller cost-per-price value than the given threshold. The procedure not only reduces the computational requirements for the local search significantly but also keeps the solution quality compared to the results without the granularity condition. Also, we use the short-term memory procedure from the tabu search heuristic to prevent the repetition in a sequence of solutions. Test results show that the mathematical formulation is difficult to solve with commercial optimization software due to the NP-hardness. Also, we analyze the algorithm’s performance with various value of granular threshold, and the results show the advantages of the granularity condition.