International Journal of Mathematics Trends and Technology
Volume 70 | Issue 9 | Year 2024 | Article Id. IJMTT-V70I9P104 | DOI : https://doi.org/10.14445/22315373/IJMTT-V70I9P104
| Received | Revised | Accepted | Published |
|---|---|---|---|
| 27 Jul 2024 | 29 Aug 2024 | 16 Sep 2024 | 30 Sep 2024 |
Many real-life optimization problems consist of multiple well known problems which are interconnected with each
other. A recent example of such a problem is the Travelling Thief Problem (TTP) or Packing While Travelling Problem (PWTP),
which combines the classical Travelling Salesman problem and the Knapsack problem. In this paper, heuristics for a variant of
PWTP, namely the PWTP with dropping rate (PWTP_DR), are examined. In PWTP_DR, a vehicle with a fixed-capacity
container visits several cities exactly once. These cities contain various items that have specific profits and weights assigned to
them. The vehicle has to pick up the items from the cities while meeting the container capacity constraint. In the process, the
vehicle's speed decreases as the weight of the container increases, while the profit associated with an item drops by a factor
called dropping rate, which depends on the duration of the article in the container. The problem is to maximize the total profit
while minimizing the tour time. So far, this problem has not received much attention, with the only exception of the well-known
NSGAII based metaheuristic (NSGAII_PWTP_DR) that utilizes a construction heuristic to create a population of initial solutions,
which then evolves through an iterative process. In this work, three heuristics tailored to the problem are designed, and their
various combinations are investigated with an aim to achieve a well-diversified population. Comprehensive experiments
supported by statistical tests provide the best combination of heuristics to generate a population of solutions as it yields results
that are significantly better than those obtained by the previously proposed NSGAII_PWTP_DR.
Bi-objective optimization problem, NSGAII, Heuristic, Travelling thief problem, Dropping rate, Packing While
Trravelling Problem.
[1] Mohammad Reza Bonyadi, Zbigniew Michalewicz, and Luigi Barone, “The Travelling Thief Problem: The First Step in the Transition
from Theoretical Problems to Realistic Problems,” 2013 IEEE Congress on Evolutionary Computation, Cancun, Mexico, pp. 1037-1044,
2013.
[CrossRef] [Google Scholar] [Publisher Link]
[2] David Pisinger, “A Minimal Algorithm for the 0-1 Knapsack Problem,” Operations Research, vol. 45, no. 7, pp. 758-767, 1997.
[CrossRef] [Google Scholar] [Publisher Link]
[3] David Applegate, William Cook, and André Rohe, “Chained Lin-Kernighan for Large Traveling Salesman Problems,” Informs Journal
on Computing, vol. 15, no. 1, pp. 82-92, 2013.
[CrossRef] [Google Scholar] [Publisher Link]
[4] S. Polyakovskiy, and F. Neumann, “The Packing while Travelling Problem,” European Journal of Operational Research, vol. 258, no. 2,
pp. 424-439, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[5] Sergey Polyakovskiy et al., “A Comprehensive Benchmark Set and Heuristics for The Travelling Thief Problem,” GECCO ‘14:
Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 477-484, Vancouver BC Canada, 2014.
[CrossRef] [Google Scholar] [Publisher Link]
[6] Julian Blank, Kalyanmoy Deb, and Sanaz Mostaghim, “Solving the Bi-objective Traveling Thief Problem with Multi-objective
Evolutionary Algorithms,” 9
th International Conference on Evolutionary Multi-Criterion Optimization, Evolutionary Multi-Criterion
Optimization, Münster, Germany, pp. 46-60, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[7] Mohammad Reza Bonyadi et al., “Socially Inspired Algorithms for the Travelling Thief Problem,” GECCO ‘14: Proceedings of the 2014
Annual Conference on Genetic and Evolutionary Computation, Vancouver BC Canada, pp. 421-428, 2014.
[CrossRef] [Google Scholar] [Publisher Link]
[8] Yi Mei, Xiaodong Li, and Xin Yao, “On Investigation of Interdependence Between Sub-Problem of the Travelling Thief Problem,” Soft
Computing, vol. 20, pp. 157-172, 2016.
[CrossRef] [Google Scholar] [Publisher Link]
[9] Junhua Wu et al., “Exact Approaches for the Travelling Thief Problem,” 11th International Conference Simulated Evolution and Learning,
Shenzhen, China, pp. 110-121, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[10] Mohamed El Yafrani et al., “A Fitness Landscape Analysis of the Travelling Thief Problem,” GECCO ‘18: Proceedings of the Genetic
and Evolutionary Computation Conference, Kyoto Japan, pp. 277-284, 2018.
[CrossRef] [Google Scholar] [Publisher Link]
[11] Alenrex Maity, and Swagatam Das, “Efficient Hybrid Local Search Heuristics for Solving the Travelling Thief Problem,” Applied Soft
Computing, vol. 93, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[12] Daniel Rodríguez et al., “A Sequence-Based Hyper-Heuristic for Travelling Thieves,” Applied Sciences, vol. 13, no. 1, pp. 1-23, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[13] Junfeng Chen et al., “Influence of Subproblem Solutions on the Quality of Traveling Thief Problem Solutions,” Journal of Intelligent and
Fuzzy Systems, vol. 44, no. 2, pp. 1943-1956, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[14] Junhua Wu et al., “Evolutionary Computation Plus Dynamic Programming for the Bi-Objective Travelling Thief Problem,” GECCO ‘18:
Proceedings of the Genetic and Evolutionary Computation Conference, Kyoto, Japan, pp. 777-784, 2018.
[CrossRef] [Google Scholar] [Publisher Link]
[15] Maciej Laszczyk, and Paweł B. Myszkowski, “A Specialized Evolutionary Approach to the bi-objective Travelling Thief Problem,”
Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, vol. 18, pp. 47-56, 2019.
[CrossRef] [Google Scholar] [Publisher Link]
[16] Rani Kumari, and Kamal Srivastava, “Variable Neighbourhood Search for Bi-objective Travelling Thief Problem,” 2020 8th International
Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions) (ICRITO), Noida, India, pp. 47-51,
2020.
[CrossRef] [Google Scholar] [Publisher Link]
[17] Jonatas B. C. Chagas et al., “A Non-Dominated Sorting Based Customized Random-Key Genetic Algorithm for the Bi-Objective Traveling
Thief Problem,” Journal of Heuristics, vol. 27, pp. 267-301, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[18] Jonatas B. C. Chagas, and Markus Wagner, “A Weighted-Sum Method for Solving the Bi-Objective Traveling Thief Problem,” Computers
and Operations Research, vol. 138, 2022.
[CrossRef] [Google Scholar] [Publisher Link]
[19] Rani Kumari, and Kamal Srivastava, “NSGAII for Travelling Thief Problem with Dropping Rate,” 7th International Conference on
Intelligent Computing and Control Systems (ICICCS), Madurai, India, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
Rani Kumari, Kamal Srivastava, "Comparison of Heuristics for Packing While Travelling Problem with Dropping Rate," International Journal of Mathematics Trends and Technology (IJMTT), vol. 70, no. 9, pp. 26-34, 2024. Crossref, https://doi.org/10.14445/22315373/IJMTT-V70I9P104
PDF 
Abstract 
Keywords 
References 
Citation