An exact \(\epsilon\)-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits

DOI10.1016/J.EJOR.2007.12.014zbMath1179.90274OpenAlexW1980201624MaRDI QIDQ953423

Jean-François Bérubé, Michel Gendreau, Jean-Yves Potvin

Publication date: 20 November 2008

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.12.014

zbMATH Keywords

branch-and-cutPareto fronttraveling salesman problem with profitsbi-objective combinatorial optimization\(\epsilon\)-constraint problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Multi-objective and goal programming (90C29) Combinatorial optimization (90C27)

Related Items (65)

A new multi-objective competitive open vehicle routing problem solved by particle swarm optimization ⋮ A bi-objective approach to discrete cost-bottleneck location problems ⋮ Column generation algorithms for bi-objective combinatorial optimization problems with a min-max objective ⋮ Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems ⋮ An exact scalarization method with multiple reference points for bi-objective integer linear optimization problems ⋮ A green-oriented bi-objective disassembly line balancing problem with stochastic task processing times ⋮ Effective methods for solving the bi-criteria \(p\)-center and \(p\)-dispersion problem ⋮ Modelling the mobile target covering problem using flying drones ⋮ UAV routing for reconnaissance mission: a multi-objective orienteering problem with time-dependent prizes and multiple connections ⋮ A multi-criteria approach for hospital capacity analysis ⋮ A multi-objective military system of systems architecting problem with inflexible and flexible systems: formulation and solution methods ⋮ Approximation schemes for bi-objective combinatorial optimization and their application to the TSP with profits ⋮ An exact solution approach for multi-objective location-transportation problem for disaster response ⋮ A math-heuristic for the warehouse location-routing problem in disaster relief ⋮ \(p\)-median and \(p\)-dispersion problems: a bi-criteria analysis ⋮ Bi-objective orienteering for personal activity scheduling ⋮ Energy-efficient bi-objective single-machine scheduling with power-down mechanism ⋮ Exact algorithms for bi-objective ring tree problems with reliability measures ⋮ Multi-directional local search ⋮ Many-objective Pareto local search ⋮ The bi-objective insular traveling salesman problem with maritime and ground transportation costs ⋮ ILP heuristics and a new exact method for bi-objective 0/1 ILPs: application to fttx-network design ⋮ A robust multi-objective model for managing the distribution of perishable products within a green closed-loop supply chain ⋮ A hybrid approach for biobjective optimization ⋮ Carrier collaboration with the simultaneous presence of transferable and non-transferable utilities ⋮ The orienteering problem with variable profits ⋮ Balancing profits and costs on trees ⋮ Branch-and-Bound for Biobjective Mixed-Integer Linear Programming ⋮ A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling: a mixed graph coloring approach ⋮ A novel multi-objective green vehicle routing and scheduling model with stochastic demand, supply, and variable travel times ⋮ Column generation based heuristics for a generalized location routing problem with profits arising in space exploration ⋮ An integrated solution approach for multi-objective, multi-skill workforce scheduling and routing problems ⋮ The orienteering problem: a survey ⋮ A versatile optimization framework for sustainable post-disaster building reconstruction ⋮ The daily routing and scheduling problem of home health care: based on costs and participants’ preference satisfaction ⋮ An extended ϵ‐constraint method for a multiobjective finite‐horizon Markov decision process ⋮ The exam location problem: mathematical formulations and variants ⋮ Bi-objective optimization of single-machine batch scheduling under time-of-use electricity prices ⋮ A new bi-objective location-routing problem for distribution of perishable products: evolutionary computation approach ⋮ A multi-objective linear programming model for scheduling part families and designing a group layout in cellular manufacturing systems ⋮ A novel model for sustainable waste collection arc routing problem: Pareto-based algorithms ⋮ Multi-objective decision method for airport landside rapid transit network design ⋮ Freshness-driven vehicle routing problem: modeling and application to the fresh agricultural product pick-storage-transportation ⋮ An interactive algorithm for multi-objective route planning ⋮ Exact hybrid algorithms for solving a bi-objective vehicle routing problem ⋮ Bi-objective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets ⋮ An interactive approach for biobjective integer programs under quasiconvex preference functions ⋮ Variants of the \(\varepsilon\)-constraint method for biobjective integer programming problems: application to \(p\)-median-cover problems ⋮ Bi-objective approaches for home healthcare medical team planning and scheduling problem ⋮ Whole blood or apheresis donations? A multi-objective stochastic optimization approach ⋮ A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems ⋮ An optimization-based heuristic for the multi-objective undirected capacitated arc routing problem ⋮ An improved approximation algorithm for the maximum TSP ⋮ A multi-objective districting problem applied to agricultural machinery maintenance service network ⋮ Multiobjective optimization for multimode transportation problems ⋮ A Tabu search algorithm for the probabilistic orienteering problem ⋮ A new bi-objective periodic vehicle routing problem with maximization market share in an uncertain competitive environment ⋮ Designing flexible loop-based material handling AGV paths with cell-adjacency priorities: an efficient cutting-plane algorithm ⋮ A Generic Branch-and-Cut Algorithm for Multiobjective Optimization Problems: Application to the Multilabel Traveling Salesman Problem ⋮ Bi-objective optimization models for network interdiction ⋮ Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems ⋮ An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem ⋮ Interactive bicriterion decision support for a large scale industrial scheduling system ⋮ Blood supply planning during natural disasters under uncertainty: a novel bi-objective model and an application for red crescent ⋮ An effective PSO-inspired algorithm for the team orienteering problem

Uses Software

• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The bi-objective covering tour problem
• The selective travelling salesman problem
• A bicriterion shortest path algorithm
• Nonlinear multiobjective optimization
• The traveling salesman problem and its variations
• The biobjective travelling purchaser problem
• An improved algorithm for solving biobjective integer programs
• Algorithm robust for the bicriteria discrete optimization problem
• An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method
• The Multiobjective Discrete Optimization Problem: A Weighted Min-Max Two-Stage Optimization Approach and a Bicriteria Algorithm
• AN ALGORITHM FOR SINGLE CONSTRAINT MAXIMUM COLLECTION PROBLEM
• The prize collecting traveling salesman problem
• TSPLIB—A Traveling Salesman Problem Library
• Facets of the knapsack polytope
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Solving the Orienteering Problem through Branch-and-Cut
• The prize collecting traveling salesman problem: II. Polyhedral results
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• A Bibliographic Survey of the Activities and International Nature of Multiple Criteria Decision Making

This page was built for publication: An exact \(\epsilon\)-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits