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

DOI10.1016/J.EJOR.2007.12.014zbMATH Open1179.90274OpenAlexW1980201624MaRDI QIDQ953423FDOQ953423

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

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

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)

Cites Work

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

Cited In (76)

• Shore hydrogen deployment problem in green ports
• The bus rapid transit investment problem
• Multi-objective decision method for airport landside rapid transit network design
• A versatile optimization framework for sustainable post-disaster building reconstruction
• 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
• An extended ϵ‐constraint method for a multiobjective finite‐horizon Markov decision process
• The multiobjective traveling salesman-repairman problem with profits: design and implementation of a variable neighborhood descent algorithm for a real scenario
• Bi-objective branch-and-cut algorithms based on LP relaxation and bound sets
• A novel model for sustainable waste collection arc routing problem: Pareto-based algorithms
• UAV routing for reconnaissance mission: a multi-objective orienteering problem with time-dependent prizes and multiple connections
• The exam location problem: mathematical formulations and variants
• 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
• Parallel implementation of an exact two-phase method for the biobjective knapsack problem
• Freshness-driven vehicle routing problem: modeling and application to the fresh agricultural product pick-storage-transportation
• Logic-based benders decomposition for bi-objective parallel machine selection and job scheduling with release dates and resource consumption
• 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
• The orienteering problem: a survey
• Blood supply planning during natural disasters under uncertainty: a novel bi-objective model and an application for red crescent
• Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems
• An improved approximation algorithm for the maximum TSP
• 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
• The daily routing and scheduling problem of home health care: based on costs and participants’ preference satisfaction
• 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 orienteering problem with variable profits
• A multi-objective districting problem applied to agricultural machinery maintenance service network
• A tabu search algorithm for the probabilistic orienteering problem
• Branch-and-Bound for Biobjective Mixed-Integer Linear Programming
• Multi-directional local search
• 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
• Bi-objective optimization models for network interdiction
• 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
• 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
• 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
• 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
• An interactive approach for biobjective integer programs under quasiconvex preference functions
• A bi-objective approach to discrete cost-bottleneck location problems
• Interactive bicriterion decision support for a large scale industrial scheduling system
• An interactive algorithm for multi-objective route planning
• A multi-objective linear programming model for scheduling part families and designing a group layout in cellular manufacturing systems
• A unified matheuristic for solving multi-constrained traveling salesman problems with profits
• An exact method for solving the bi-objective minimum diameter-cost spanning tree problem
• Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems

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)