.png){kind=icon}
返回
The Packing While Traveling Problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2016.09.035.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 MP-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 programing (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 programing 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. (C) 2016 Elsevier B.V. All rights reserved.
Keyword:
Combinatorial optimization
Non-linear knapsack problem
Linearization technique
Piecewise approximation
Hybrid optimization
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
Injury-Dependent and Disability-Specific Lumbar Spinal Gene Regulation following Sciatic Nerve Injury in the Rat大鼠坐骨神经损伤后损伤依赖性和残疾特异性腰椎基因调控.png)
PLOS ONEOAAI
PLOS ONEIF0
OAAI分享收藏On investigation of interdependence between sub-problems of the Travelling Thief ProblemSOFT COMPUTINGOAAI
SOFT COMPUTINGIF2.5
OAAI分享收藏分享收藏
查看更多内容