A tabu search algorithm for the open vehicle routing problem.

*(English)*Zbl 1068.90026Summary: The problem studied in this paper is different from the basic vehicle routing problem in that the vehicles do not return to the distribution depot after delivering the goods to the customers or, if they do so, they must visit the same customers, for the collection of goods, in the reverse order. The practical importance of this problem has been established some decades ago, but it has received very little attention from researchers. In this paper we present a new tabu search algorithm that explores the structure of this type of problem and we compare its performance with another heuristic designed for the same purpose, which has been published recently.

##### Software:

VRP
Full Text:
DOI

##### References:

[1] | Bodin, L.; Golden, B.; Assad, A.; Ball, M., Routing and scheduling of vehicles and crews: the state of the art, Computers and operations research, 10, 2, 63-211, (1983) |

[2] | Brandão, J., A lower bound based meta-heuristic for the vehicle routing problem, (), 151-168 · Zbl 1006.90018 |

[3] | Brandão, J.; Mercer, A., A tabu search algorithm for the multi-trip vehicle routing and scheduling problem, European journal of operational research, 100, 1, 180-191, (1997) · Zbl 0947.90578 |

[4] | Brandão, J.; Mercer, A., The multi-trip vehicle routing problem, Journal of the operational research society, 49, 799-805, (1998) · Zbl 1140.90329 |

[5] | Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (), 313-338 |

[6] | Christofides, N.; Mingozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relations, Mathematical programming, 20, 255-282, (1981) · Zbl 0461.90067 |

[7] | Crainic, T.; Laporte, G., Fleet management and logistics, (1998), Kluwer Academic Publishers · Zbl 0933.00021 |

[8] | Fisher, M., Optimal solution of vehicle routing problems using minimum k-trees, Operations research, 42, 4, 626-642, (1994) · Zbl 0815.90066 |

[9] | Fisher, M., A polynomial algorithm for the degree-constrained minimum k-tree problem, Operations research, 42, 4, 775-779, (1994) · Zbl 0815.90131 |

[10] | Gendreau, M.; Hertz, A.; Laporte, G., New insertion and post-optimization procedures for the traveling salesman problem, Operations research, 40, 6, 1086-1094, (1992) · Zbl 0767.90087 |

[11] | Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing, Management science, 40, 10, 1276-1290, (1994) · Zbl 0822.90053 |

[12] | Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms, European journal of operational research, 59, 3, 345-358, (1992) · Zbl 0761.90034 |

[13] | Osman, I., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, (), 421-451 · Zbl 0775.90153 |

[14] | Rochat, Y.; Taillard, E., Probabilistic diversification and intensification in local search for vehicle routing, Journal of heuristics, 1, 147-167, (1995) · Zbl 0857.90032 |

[15] | Sariklis, D.; Powell, S., A heuristic method for the open vehicle routing problem, Journal of the operational research society, 51, 564-573, (2000) · Zbl 1055.90530 |

[16] | Schrage, L., Formulation and structure of more complex/realistic routing and scheduling problems, Networks, 11, 229-232, (1981) |

[17] | Syslo, M.; Deo, N.; Kowaklik, J., Discrete optimization algorithms with Pascal programs, (1983), Prentice Hall, Inc |

[18] | Taillard, E., Parallel iterative search methods for the vehicle routing problems, Networks, 23, 661-673, (1993) · Zbl 0804.90045 |

[19] | Toth, P., Vigo, D., submitted. The granular tabu search (and its application to the vehicle routing problem). INFORMS Journal on Computing, submitted for publication · Zbl 1238.90141 |

[20] | Van Breedam, A., Comparing descent heuristics and metaheuristics for the vehicle routing problem, Computers and operations research, 28, 289-315, (2001) · Zbl 0976.90018 |

[21] | Xu, J.; Kelly, J., A network flow-based tabu search heuristic for the vehicle routing problem, Transportation science, 30, 379-393, (1996) · Zbl 0879.90086 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.