The vehicle routing problem with simultaneous deliveries and pickups (VRPSDP) has attracted much research interest because of the potential to provide cost savings to transportation and logistics operators. Several extensions of VRPSDP exist. Of these extensions, the simultaneous deliveries and pickups with split loads problem (SDPSLP) has been proposed to eliminate vehicle capacity constraints, as well as allow the deliveries or pickups for a customer to be split into multiple visits. Although delivery and pickup activities are often constrained by time windows, few studies have considered such constraints when SDPSLP has been addressed. To fill the gap, this paper formulates the vehicle routing problem of simultaneous deliveries and pickups with split loads and time windows (VRPSDPSLTW) as a mixed-integer programming problem. A hybrid heuristic algorithm was developed to solve this problem. Solomon data sets with minor modifications were applied to test the effectiveness of the solution algorithm. The results of a computational experiment demonstrated that use of the proposed algorithms to solve VRPSDPSLTW had advantages for minimization of the total travel cost, number of vehicles, and loading rate. The proposed formulation and solution algorithm for VRPSDPSLTW may serve as a general analytical tool for the optimization of vehicle routing in practice.
Get full access to this article
View all access options for this article.
References
1.
PaessensH.The Savings Algorithm for the Vehicle Routing Problem. European Journal of Operational Research, Vol. 34, No. 3, 1988, pp. 336–344.
2.
BelenguerJ. M., MartinezM. C., and MotaE.A Lower Bound for the Split Delivery Vehicle Routing Problem. Operations Research, Vol. 48, No. 5, 2000, pp. 801–810.
3.
ArchettiC., SavelsberghM. W. P., and SperanzaM. G.To Split or Not to Split: That Is the Question. Transportation Research Part E, Vol. 44, No. 1, 2008, pp. 114–123.
4.
SolomonM.Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, Vol. 35, No. 2, 1987, pp. 254–265.
5.
GoetschalckxM., and Jacobs-BlechaC.The Vehicle Routing Problem with Backhauls. European Journal of Operational Research, Vol. 42, No. 1, 1989, pp. 39–51.
6.
LaporteG.The Vehicle Routing Problem: An Over View of Exact and Approximate Algorithms. European Journal of Operational Research, Vol. 59, No. 3, 1992, pp. 345–358.
7.
DrorM., and TrudeauP.Savings by Split Delivery Routing. Transportation Science, Vol. 23, No. 2, 1989, pp. 141–145.
8.
DrorM., LaporteG., and TrudeauP.Vehicle Routing with Split Deliveries. Discrete Applied Mathematics, Vol. 50, No. 3, 1994, pp. 239–254.
9.
GulczynskiD., GoldenB., and WasilE.The Split Delivery Vehicle Routing Problem with Minimum Delivery Amounts. Transportation Research Part E, Vol. 46, No. 5, 2010, pp. 612–626.
10.
TingC.-J., and ChenC.-H.Combination of Multiple Ant Colony System and Simulated Annealing for the Multidepot Vehicle-Routing Problem with Time Windows. In Transportation Research Record: Journal of the Transportation Research Board, No. 2089, Transportation Research Board of the National Academies, Washington, D.C., 2008, pp. 85–92.
11.
ArchettiC., SperanzaM. G., and HertzA.A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem. Transportation Science, Vol. 40, No. 1, 2006, pp. 64–73.
12.
JinM. Z., LiuK., and BowdenR. O.A Two-Stage Algorithm with Valid Inequalities for the Split Delivery Vehicle Routing Problem. International Journal of Production Economics, Vol. 105, No. 1, 2007, pp. 228–242.
13.
JinM. Z., LiuK., and EksiogluB.A Column Generation Approach for the Split Delivery Vehicle Routing Problem. Operations Research Letters, Vol. 58, No. 4, 2008, pp. 265–270.
14.
LeeC. G., EpelmanM., WhiteC. C.III, and BozerY. A.A Shortest Path Approach to the Multiple-Vehicle Routing Problem with Split Pick-Ups. Transportation Research Part B, Vol. 40, No. 4, 2006, pp. 265–284.
15.
FrizzellP. W., and GiffinJ. W.The Split Delivery Vehicle Scheduling Problem with Time Windows and Grid Network Distance. Computers & Operations Research, Vol. 22, No. 6, 1995, pp. 655–667.
16.
HoS. C., and HauglandD.A Tabu Search Heuristic for Vehicle Routing Problem with Time Windows and Split Deliveries. Computers & Operations Research, Vol. 31, No. 12, 2004, pp. 1947–1964.
17.
BelfioreP., and YoshizakiH. T. Y.Scatter Search for a Real-Life Hetero geneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries in Brazil. European Journal of Operational Research, Vol. 199, No. 3, 2009, pp. 750–758.
18.
SalaniM., and VaccaI.Branch and Price for the Vehicle Routing Problem with Discrete Split Deliveries and Time Windows. European Journal of Operational Research, Vol. 213, No. 3, 2011, pp. 470–477.
19.
ArchettiC., BouchardM., and DesaulniersG.Enhanced Branch and Price and Cut for Vehicle Routing with Split Deliveries and Time Windows. Transportation Science, Vol. 45, No. 3, 2011, pp. 285–298.
20.
ChenJ. F., and WuT. H.Vehicle Routing Problem with Simultaneous Deliveries and Pickups. Journal of the Operational Research Society, Vol. 57, No. 5, 2006, pp. 579–587.
21.
MitraS.A Parallel Clustering Technique for the Vehicle Routing Problem with Split Deliveries and Pickups. Journal of the Operational Research Society, Vol. 59, No. 11, 2008, pp. 1532–1546.
22.
KumarR., UnnikrishnanA., and WallerS. T.Capacitated-Vehicle Routing Problem with Backhauls on Trees: Model, Properties, Formulation, and Algorithm. In Transportation Research Record: Journal of the Transportation Research Board, No. 2263, Transportation Research Board of the National Academies, Washington, D.C., 2011, pp. 92–102.
23.
NanryW. P., and BarnesJ. W.Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search. Transportation Research Part B, Vol. 34, No. 2, 2000, pp. 107–121.
24.
LuQ., and MagedM. D.A New Insertion-Based Construction Heuristic for Solving the Pickup and Delivery Problem with Time Windows. European Journal of Operational Research, Vol. 175, No. 2, 2006, pp. 672–687.
25.
NowakM., ErgunO., and WhiteC. C.IIIAn Empirical Study on the Benefit of Split Loads with the Pickup and Delivery Problem. European Journal of Operational Research, Vol. 198, No. 3, 2009, pp. 734–740.
26.
KorsvikJ. E., FagerholtK., and LaporteG.A Large Neighbourhood Search Heuristic for Ship Routing and Scheduling with Split Loads. Computers & Operations Research, Vol. 38, No. 2, 2011, pp. 474–483.
27.
MullaserilP. A., DrorM., and LeungJ.Split-Delivery Routing Heuristics in Livestock Feed Distribution. Journal of the Operational Research Society, Vol. 48, No. 2, 1997, pp. 107–116.
28.
PotvinJ. Y., KervahutT., GarciaB. L., and RousseauJ. M.A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows.Technical report CRT-855. University de Montreal, Montreal, Quebec, Canada, 1992.
29.
LinS.Computer Solution of the TSP. Bell System Technical Journal, Vol. 44, No. 1, 1965, pp. 2245–2269.
30.
OrI.Traveling Salesman-Type Combinational Problems and Their Relation to the Logistics of Blood Banking.PhD thesis. Northwestern University, Chicago, Ill., 1976.
FigliozziM. A.The Time Dependent Vehicle Routing Problem with Time Windows: Benchmark Problems, an Efficient Solution Algorithm, and Solution Characteristics. Transportation Research Part E, Vol. 48, No. 3, 2012, pp. 616–636.
