The bi-objective traveling purchaser problem with deliveries

Pamela Jocelyn Palomo Martinez, M. Angélica Salazar-Aguilar

Research output: Contribution to journalArticle

Abstract

In this work we introduce a variant of the well-known Traveling Purchaser Problem in which the purchased products must be delivered to a set of customers. The objective is to minimize the total cost (purchasing plus traveling costs) and the waiting time of the customers, simultaneously, while satisfying the total demand. This problem is called the bi-objective Traveling Purchaser Problem with Deliveries. In order to approximate Pareto fronts for this problem, a relinked variable neighborhood search is proposed and tested over a large set of artificial instances. Our results show that our algorithm is highly competitive compared to the ϵ-constraint method in small instances. On the other hand, experiments carried out over large instances show that our algorithm is able to find Pareto front approximations with more points in a shorter running time for uncapacitated instances than for capacitated ones. Also, computational results show that the performance of some local searches used in our algorithm depends on the characteristics of the instances, this underlines the importance of designing a metaheuristic based on multiple local searches.
Original languageEnglish
Pages (from-to)608-622
Number of pages15
JournalEuropean Journal of Operational Research
Volume273
Issue number2
DOIs
Publication statusPublished - Mar 2019
Externally publishedYes

Fingerprint

Pareto Front
Local Search
Customers
Purchasing
Variable Neighborhood Search
Costs
Waiting Time
Metaheuristics
Large Set
Computational Results
Minimise
Approximation
Experiments
Experiment
Local search
Pareto
Waiting time
Variable neighborhood search
Demand

Cite this

@article{fa7f2281ac11446085f65af4598356fe,
title = "The bi-objective traveling purchaser problem with deliveries",
abstract = "In this work we introduce a variant of the well-known Traveling Purchaser Problem in which the purchased products must be delivered to a set of customers. The objective is to minimize the total cost (purchasing plus traveling costs) and the waiting time of the customers, simultaneously, while satisfying the total demand. This problem is called the bi-objective Traveling Purchaser Problem with Deliveries. In order to approximate Pareto fronts for this problem, a relinked variable neighborhood search is proposed and tested over a large set of artificial instances. Our results show that our algorithm is highly competitive compared to the ϵ-constraint method in small instances. On the other hand, experiments carried out over large instances show that our algorithm is able to find Pareto front approximations with more points in a shorter running time for uncapacitated instances than for capacitated ones. Also, computational results show that the performance of some local searches used in our algorithm depends on the characteristics of the instances, this underlines the importance of designing a metaheuristic based on multiple local searches.",
author = "{Palomo Martinez}, {Pamela Jocelyn} and Salazar-Aguilar, {M. Ang{\'e}lica}",
year = "2019",
month = "3",
doi = "10.1016/j.ejor.2018.08.039",
language = "English",
volume = "273",
pages = "608--622",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "2",

}

The bi-objective traveling purchaser problem with deliveries. / Palomo Martinez, Pamela Jocelyn; Salazar-Aguilar, M. Angélica.

In: European Journal of Operational Research, Vol. 273, No. 2, 03.2019, p. 608-622.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The bi-objective traveling purchaser problem with deliveries

AU - Palomo Martinez, Pamela Jocelyn

AU - Salazar-Aguilar, M. Angélica

PY - 2019/3

Y1 - 2019/3

N2 - In this work we introduce a variant of the well-known Traveling Purchaser Problem in which the purchased products must be delivered to a set of customers. The objective is to minimize the total cost (purchasing plus traveling costs) and the waiting time of the customers, simultaneously, while satisfying the total demand. This problem is called the bi-objective Traveling Purchaser Problem with Deliveries. In order to approximate Pareto fronts for this problem, a relinked variable neighborhood search is proposed and tested over a large set of artificial instances. Our results show that our algorithm is highly competitive compared to the ϵ-constraint method in small instances. On the other hand, experiments carried out over large instances show that our algorithm is able to find Pareto front approximations with more points in a shorter running time for uncapacitated instances than for capacitated ones. Also, computational results show that the performance of some local searches used in our algorithm depends on the characteristics of the instances, this underlines the importance of designing a metaheuristic based on multiple local searches.

AB - In this work we introduce a variant of the well-known Traveling Purchaser Problem in which the purchased products must be delivered to a set of customers. The objective is to minimize the total cost (purchasing plus traveling costs) and the waiting time of the customers, simultaneously, while satisfying the total demand. This problem is called the bi-objective Traveling Purchaser Problem with Deliveries. In order to approximate Pareto fronts for this problem, a relinked variable neighborhood search is proposed and tested over a large set of artificial instances. Our results show that our algorithm is highly competitive compared to the ϵ-constraint method in small instances. On the other hand, experiments carried out over large instances show that our algorithm is able to find Pareto front approximations with more points in a shorter running time for uncapacitated instances than for capacitated ones. Also, computational results show that the performance of some local searches used in our algorithm depends on the characteristics of the instances, this underlines the importance of designing a metaheuristic based on multiple local searches.

UR - http://dx.doi.org/10.1016/j.ejor.2018.08.039

U2 - 10.1016/j.ejor.2018.08.039

DO - 10.1016/j.ejor.2018.08.039

M3 - Article

VL - 273

SP - 608

EP - 622

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -