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

DOI10.1016/J.EJOR.2007.12.014MaRDI QIDQ953423zbMATH OpenOpenAlexFDO

Authors J. 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

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

Recommendations

• A two-phase method for bi-objective combinatorial optimization and its application to the TSP with profits
• An \(\varepsilon \)-constraint column generation-and-enumeration algorithm for bi-objective vehicle routing problems
• Exact hybrid algorithms for solving a bi-objective vehicle routing problem
• Multi-objective meta-heuristics for the traveling salesman problem with profits
• An exact algebraic \(\epsilon \)-constraint method for bi-objective linear integer programming based on test sets

Cites work

• scientific article; zbMATH DE number 3833720 (Why is no real title available?)
• scientific article; zbMATH DE number 2064416 (Why is no real title available?)
• scientific article; zbMATH DE number 2160609 (Why is no real title available?)
• scientific article; zbMATH DE number 2102227 (Why is no real title available?)
• scientific article; zbMATH DE number 915988 (Why is no real title available?)
• scientific article; zbMATH DE number 2209474 (Why is no real title available?)
• A Bibliographic Survey of the Activities and International Nature of Multiple Criteria Decision Making
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• A bicriterion shortest path algorithm
• AN ALGORITHM FOR SINGLE CONSTRAINT MAXIMUM COLLECTION PROBLEM
• Algorithm robust for the bicriteria discrete optimization problem
• An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method
• An improved algorithm for solving biobjective integer programs
• Facets of the knapsack polytope
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Nonlinear multiobjective optimization
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• Solving the Orienteering Problem through Branch-and-Cut
• TSPLIB—A Traveling Salesman Problem Library
• The bi-objective covering tour problem
• The biobjective travelling purchaser problem
• The multiobjective discrete optimization problem: a weighted min-max two-stage optimization approach and a bicriteria algorithm
• The prize collecting traveling salesman problem
• The prize collecting traveling salesman problem: II. Polyhedral results
• The selective travelling salesman problem
• The traveling salesman problem and its variations

Cited in

(76)

• Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems
• A generic branch-and-cut algorithm for multiobjective optimization problems: application to the multilabel traveling salesman problem
• A new multi-objective competitive open vehicle routing problem solved by particle swarm optimization
• A green-oriented bi-objective disassembly line balancing problem with stochastic task processing times
• An exact scalarization method with multiple reference points for bi-objective integer linear optimization problems
• Bi-objective approaches for home healthcare medical team planning and scheduling problem
• Shore hydrogen deployment problem in green ports
• The orienteering problem: a survey
• Blood supply planning during natural disasters under uncertainty: a novel bi-objective model and an application for red crescent
• The bus rapid transit investment problem
• Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems
• An improved approximation algorithm for the maximum TSP
• Multi-objective decision method for airport landside rapid transit network design
• Column generation algorithms for bi-objective combinatorial optimization problems with a min-max objective
• Carrier collaboration with the simultaneous presence of transferable and non-transferable utilities
• Many-objective Pareto local search
• Modelling the mobile target covering problem using flying drones
• Multi-objective meta-heuristics for the traveling salesman problem with profits
• Variants of the \(\varepsilon\)-constraint method for biobjective integer programming problems: application to \(p\)-median-cover problems
• Multiobjective optimization for multimode transportation problems
• A new bi-objective periodic vehicle routing problem with maximization market share in an uncertain competitive environment
• A math-heuristic for the warehouse location-routing problem in disaster relief
• The daily routing and scheduling problem of home health care: based on costs and participants’ preference satisfaction
• A multi-objective districting problem applied to agricultural machinery maintenance service network
• A versatile optimization framework for sustainable post-disaster building reconstruction
• The orienteering problem with variable profits
• A tabu search algorithm for the probabilistic orienteering problem
• A new fuzzy approach of vehicle routing problem for disaster-stricken zones
• Fuzzy planning model for the shelters location and victims evacuation in the disaster-stricken zone
• Branch-and-Bound for Biobjective Mixed-Integer Linear Programming
• An extended ϵ‐constraint method for a multiobjective finite‐horizon Markov decision process
• Multi-directional local search
• Bi-objective branch-and-cut algorithms based on LP relaxation and bound sets
• UAV routing for reconnaissance mission: a multi-objective orienteering problem with time-dependent prizes and multiple connections
• The multiobjective traveling salesman-repairman problem with profits: design and implementation of a variable neighborhood descent algorithm for a real scenario
• A novel model for sustainable waste collection arc routing problem: Pareto-based algorithms
• 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
• The bi-objective insular traveling salesman problem with maritime and ground transportation costs
• The exam location problem: mathematical formulations and variants
• A multi-criteria approach for hospital capacity analysis
• An exact solution approach for multi-objective location-transportation problem for disaster response
• A hybrid approach for biobjective optimization
• Bi-objective optimization models for network interdiction
• Exact hybrid algorithms for solving a bi-objective vehicle routing problem
• A new bi-objective location-routing problem for distribution of perishable products: evolutionary computation approach
• 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
• p-median and p-dispersion problems: a bi-criteria analysis
• Balancing profits and costs on trees
• A robust multi-objective model for managing the distribution of perishable products within a green closed-loop supply chain
• A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling: a mixed graph coloring approach
• An \(\varepsilon \)-constraint column generation-and-enumeration algorithm for bi-objective vehicle routing problems
• ILP heuristics and a new exact method for bi-objective 0/1 ILPs: application to fttx-network design
• Column generation based heuristics for a generalized location routing problem with profits arising in space exploration
• An effective PSO-inspired algorithm for the team orienteering problem
• Designing flexible loop-based material handling AGV paths with cell-adjacency priorities: an efficient cutting-plane algorithm
• An integrated solution approach for multi-objective, multi-skill workforce scheduling and routing problems
• Whole blood or apheresis donations? A multi-objective stochastic optimization approach
• A novel multi-objective green vehicle routing and scheduling model with stochastic demand, supply, and variable travel times
• A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems
• A two-phase method for bi-objective combinatorial optimization and its application to the TSP with profits
• Parallel implementation of an exact two-phase method for the biobjective knapsack problem
• Bi-objective optimization of single-machine batch scheduling under time-of-use electricity prices
• An optimization-based heuristic for the multi-objective undirected capacitated arc routing problem
• Effective methods for solving the bi-criteria \(p\)-center and \(p\)-dispersion problem
• Freshness-driven vehicle routing problem: modeling and application to the fresh agricultural product pick-storage-transportation
• An interactive approach for biobjective integer programs under quasiconvex preference functions
• An interactive algorithm for multi-objective route planning
• A bi-objective approach to discrete cost-bottleneck location problems
• Interactive bicriterion decision support for a large scale industrial scheduling system
• A unified matheuristic for solving multi-constrained traveling salesman problems with profits
• A multi-objective linear programming model for scheduling part families and designing a group layout in cellular manufacturing systems
• Logic-based benders decomposition for bi-objective parallel machine selection and job scheduling with release dates and resource consumption
• An exact method for solving the bi-objective minimum diameter-cost spanning tree problem

Describes a project that uses

Uses Software

• TSPLIB

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q953423)