期刊
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH
卷 22, 期 2, 页码 153-169出版社
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0217595905000522
关键词
vehicle routing; backhauling; mixed integer linear programming; heuristic
The Vehicle Routing Problem with Backhauling deals with the supply of finished goods from a depot to a number of delivery points, and picking up returnable items and bringing them back to the depot using a fleet of trucks. Traditionally, the objective of the problem has been to determine the truck routes such that the total number of trucks and/or the total distance traveled/total route cost are minimized. Most of the papers available in the literature in this connection deal with problems where the linehaul (having a demand for finished goods) and backhaul (having items to be returned to the depot) customers axe different, and a customer may be visited by at most one truck limiting demand and returns at a location by the capacity of the truck. In this paper, we allow the linehaul and backhaul customers to be the same leading to simultaneous delivery and pickup at a customer location, and also there is no restriction on the quantity demanded at (to be returned from) a customer location. As such a customer may be visited by more than one truck and more than once by the same truck. We developed a Mixed Integer Linear programming (MILP) formulation of the problem and a route construction heuristic. The heuristic averaged 80 ms for 110 problems tested, and in 78 of them the heuristic costs were either equal to the optimal costs or at most equal to the upper bounds on the optimal costs obtained after running the optimization package for 30 min. Optimal solutions were obtained for 28 problems at an average time of 295 ms. The heuristic could match the optimal solutions for 22 of these problems at, an average time of 71 ms.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据