 |
|||||||||
| Volume 5, Number 2, May 2009, pp. 185-202 | |||||||||
| H. Hashimoto, Y. Ezaki, M. Yagiura, K. Nonobe, T. Ibaraki and A. Løkketangen | |||||||||
| Key words: | |||||||||
| pickup and delivery problem, general constraints, set covering | |||||||||
| Mathematices Subject Classification: 05B40, 90B06, 90C27 | |||||||||
|
|||||||||
| Volume 5, Number 2, May 2009, pp. 185-202 | |||||||||
| H. Hashimoto, Y. Ezaki, M. Yagiura, K. Nonobe, T. Ibaraki and A. Løkketangen | |||||||||
| Key words: | |||||||||
| pickup and delivery problem, general constraints, set covering | |||||||||
| Mathematices Subject Classification: 05B40, 90B06, 90C27 | |||||||||
|
||||||||||||||||||||||||||||||||||||||||
| Abstract: | |||
| In this paper, we generalize the pickup and delivery problem with time windows by allowing general constraints on each route, and propose a heuristic algorithm. Our algorithm first generates a set of feasible routes, and repeats modifying the set by using the information from a Lagrangian relaxation of the set covering problem that corresponds to the current set. It then solves the resulting set covering problem to construct a good feasible solution for the original problem. We conduct computational experiments for instances with various constraints, and confirm the flexibility of our algorithm. | |||
| A set covering approach for the pickup and delivery problem with general constraints on each route | ||