×

The packing while traveling problem. (English) Zbl 1394.90494

Summary: This paper introduces the packing while traveling problem as a new non-linear knapsack problem. Given are a set of cities that have a set of items of distinct profits and weights and a vehicle that may collect the items when visiting all the cities in a fixed order. Each selected item contributes its profit, but produces a transportation cost relative to its weight. The problem asks to find a subset of the items such that the total gain is maximized. We investigate constrained and unconstrained versions of the problem and show that both are NP-hard. We propose a pre-processing scheme that decreases the size of instances making them easier for computation. We provide lower and upper bounds based on mixed-integer programming (MIP) adopting the ideas of piecewise linear approximation. Furthermore, we introduce two exact approaches: one is based on MIP employing linearization technique, and another is a branch-infer-and-bound (BIB) hybrid approach that compounds the upper bound procedure with a constraint programming model strengthened with customized constraints. Our experimental results show the effectiveness of our exact and approximate solutions in terms of solution quality and computational time.

MSC:

90C27 Combinatorial optimization
90C11 Mixed integer programming
90C30 Nonlinear programming
90C60 Abstract computational complexity for mathematical programming problems

Software:

Knapsack; TSPLIB
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Applegate, D.; Cook, W. J.; Rohe, A., Chained Lin-Kernighan for large traveling salesman problems, INFORMS Journal on Computing, 15, 1, 82-92 (2003) · Zbl 1238.90125
[2] Balas, E., The prize collecting traveling salesman problem, Networks, 19, 6, 621-636 (1989) · Zbl 0676.90089
[3] Beham, A.; Fechter, J.; Kommenda, M.; Wagner, S.; Winkler, S. M.; Affenzeller, M., Optimization strategies for integrated knapsack and traveling salesman problems, (Moreno-Díaz, R.; Pichler, F.; Quesada-Arencibia, A., Proceedings of the fifteenth international conference on computer aided systems theory - EUROCAST 2015: Las Palmas de Gran Canaria, Spain, February 8-13, 2015, Revised Selected Papers (2015), Springer International Publishing: Springer International Publishing Cham), 359-366)
[4] Bockmayr, A.; Hooker, J. N., Constraint programming, (K. Aardal, G. N.; Weismantel, R., Discrete optimization. Discrete optimization, Handbooks in operations research and management science, vol. 12 (2005), Elsevier), 559-600 · Zbl 1278.90373
[5] Bonyadi, M. R.; Michalewicz, Z.; Barone, L., The travelling thief problem: The first step in the transition from theoretical problems to realistic problems, Proceedings of the IEEE congress on evolutionary computation, CEC 2013, 1037-1044 (2013), IEEE
[6] Bretthauer, K. M.; Shetty, B., The nonlinear knapsack problem - Algorithms and applications, European Journal of Operational Research, 138, 3, 459-472 (2002) · Zbl 1003.90036
[7] Chand, S.; Wagner, M., Fast heuristics for the multiple traveling thieves problem, Proceedings of the 2016 annual conference on genetic and evolutionary computation. Proceedings of the 2016 annual conference on genetic and evolutionary computation, GECCO ’16 (2016), ACM: ACM New York, NY, USA
[8] Chekuri, C.; Khanna, S., A polynomial time approximation scheme for the multiple knapsack problem, SIAM Journal on Computing, 35, 3, 713-728 (2005) · Zbl 1095.68035
[9] Elhedhli, S., Exact solution of a class of nonlinear knapsack problems, Operations Research Letters, 33, 6, 615-624 (2005) · Zbl 1141.90510
[10] Erlebach, T.; Kellerer, H.; Pferschy, U., Approximating multi-objective knapsack problems, (Dehne, F. K.H. A.; Sack, J.-R.; Tamassia, R., Wads. Wads, Lecture notes in computer science, Vol. 2125 (2001), Springer), 210-221 · Zbl 1018.90034
[11] Faulkner, H.; Polyakovskiy, S.; Schultz, T.; Wagner, M., Approximate approaches to the traveling thief problem, Proceedings of the 2015 annual conference on genetic and evolutionary computation. Proceedings of the 2015 annual conference on genetic and evolutionary computation, GECCO ’15, 385-392 (2015), ACM: ACM New York, NY, USA
[12] Feillet, D.; Dejax, P.; Gendreau, M., Traveling salesman problems with profits, Transportation Science, 39, 2, 188-205 (2005)
[13] Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness (1979), W. H. Freeman · Zbl 0411.68039
[14] GOODYEAR (2008). Factors affecting truck fuel economy. http://www.goodyeartrucktires.com/pdf/resources/publications/FactorsAffectingTruckFuelEconomy.pdf; GOODYEAR (2008). Factors affecting truck fuel economy. http://www.goodyeartrucktires.com/pdf/resources/publications/FactorsAffectingTruckFuelEconomy.pdf
[15] Hochbaum, D. S., A nonlinear knapsack problem, Operations Research Letters, 17, 3, 103-110 (1995) · Zbl 0838.90092
[16] Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems (2004), Springer: Springer Berlin, Germany · Zbl 1103.90003
[17] Laporte, G., Fifty years of vehicle routing, Transportation Science, 43, 4, 408-416 (2009)
[18] Li, H.-L., A global approach for general 0-1 fractional programming, European Journal of Operational Research, 73, 3, 590-596 (1994) · Zbl 0806.90119
[19] Lin, C.; Choy, K.; Ho, G.; Chung, S.; Lam, H., Survey of green vehicle routing problem: Past and future trends, Expert Systems with Applications, 41, 4, Part 1, 1118-1138 (2014)
[20] Lourenço, N.; Pereira, F. B.; Costa, E., An evolutionary approach to the full optimization of the traveling thief problem, (Chicano, F.; Hu, B.; García-Sánchez, P., Proceedings of the sixteenth European conference on evolutionary computation in combinatorial optimization, EvoCOP 2016 (2016), Springer International Publishing: Springer International Publishing Cham), 34-45
[21] Martello, S.; Pisinger, D.; Toth, P., Dynamic programming and strong bounds for the 0-1 knapsack problem, Management Science, 45, 3, 414-424 (1999) · Zbl 1231.90338
[22] Martello, S.; Toth, P., Knapsack problems: Algorithms and computer implementations (1990), John Wiley & Sons · Zbl 0708.68002
[23] Mei, Y.; Li, X.; Salim, F.; Yao, X., Heuristic evolution with genetic programming for traveling thief problem, Proceedings of the 2015 IEEE congress on evolutionary computation (CEC), 2753-2760 (2015)
[24] Mei, Y.; Li, X.; Yao, X., On investigation of interdependence between sub-problems of the travelling thief problem, Soft Computing, 20, 1, 157-172 (2016)
[25] Polyakovskiy, S.; Bonyadi, M. R.; Wagner, M.; Michalewicz, Z.; Neumann, F., A comprehensive benchmark set and heuristics for the traveling thief problem, Proceedings of the 2014 annual conference on genetic and evolutionary computation. Proceedings of the 2014 annual conference on genetic and evolutionary computation, GECCO ’14, 477-484 (2014), ACM: ACM New York, NY, USA
[26] Polyakovskiy, S.; Neumann, F., Packing while traveling: Mixed integer programming for a class of nonlinear knapsack problems, (Michel, L., Integration of AI and OR techniques in constraint programming. Integration of AI and OR techniques in constraint programming, Lecture notes in computer science, vol. 9075 (2015), Springer International Publishing), 332-346 · Zbl 1459.90187
[27] Reinelt, G., TSPLIB - A traveling salesman problem library, ORSA Journal on Computing, 3, 4, 376-384 (1991) · Zbl 0775.90293
[28] Rossi, F.; van Beek, P.; Walsh, T., Chapter 4 constraint programming, (Frank van Harmelen, V. L.; Porter, B., Handbook of knowledge representation. Handbook of knowledge representation, Foundations of artificial intelligence, Vol. 3 (2008), Elsevier), 181-211
[29] Rossi, F.; Beek, P.v.; Walsh, T., Handbook of constraint programming (foundations of artificial intelligence) (2006), Elsevier Science Inc: Elsevier Science Inc New York, NY, USA
[30] Sherali, H.; Adams, W., A reformulation linearization technique for solving discrete and continuous nonconvex problems (1999), Kluwer Academic Publishing: Kluwer Academic Publishing Boston, MA · Zbl 0926.90078
[31] Tawarmalani, M.; Ahmed, S.; Sahinidis, N., Global optimization of 0-1 hyperbolic programs, Journal of Global Optimization, 24, 4, 385-416 (2002) · Zbl 1046.90054
[32] Toth, P.; Vigo, D., Vehicle routing (2014), Society for Industrial and Applied Mathematics
[33] Vansteenwegen, P.; Souffriau, W.; Oudheusden, D. V., The orienteering problem: A survey, European Journal of Operational Research, 209, 1, 1-10 (2011) · Zbl 1205.90253
[34] Westerlund, A.; Göthe-Lundgren, M.; Larsson, T., A stabilized column generation scheme for the traveling salesman subtour problem, Discrete Applied Mathematics, 154, 15, 2212-2238 (2006) · Zbl 1111.90097
[35] Wu, J.; Polyakovskiy, S.; Neumann, F., On the impact of the renting rate for the unconstrained nonlinear knapsack problem, Proceedings of the 2016 annual conference on genetic and evolutionary computation. Proceedings of the 2016 annual conference on genetic and evolutionary computation, GECCO ’16, 413-419 (2016), ACM: ACM New York, NY, USA
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.