A simple and effective metaheuristic for the minimum latency problem

DOI10.1016/j.ejor.2012.03.044zbMath1253.90012OpenAlexW2087852198MaRDI QIDQ1926884

Thibaut Vidal, Anand Subramanian, Luiz Satoru Ochi, Marcos Melo Silva

Publication date: 29 December 2012

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

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

zbMATH Keywords

metaheuristicsGRASPiterated local searchminimum latency problem

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (35)

A logic-based Benders decomposition method for the multi-trip traveling repairman problem with drones ⋮ Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem ⋮ A hybrid algorithm for a class of vehicle routing problems ⋮ An iterated local search heuristic for the split delivery vehicle routing problem ⋮ Hybrid metaheuristics for the clustered vehicle routing problem ⋮ A heuristic algorithm for a single vehicle static bike sharing rebalancing problem ⋮ Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times ⋮ A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment ⋮ Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times ⋮ A branch-and-price algorithm for the minimum latency problem ⋮ Scheduling last-mile deliveries with truck-based autonomous robots ⋮ Routing multiple work teams to minimize latency in post-disaster road network restoration ⋮ Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery ⋮ A concise guide to existing and emerging vehicle routing problem variants ⋮ A performance study on multi improvement neighborhood search strategy ⋮ Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule ⋮ Multirobot search for a stationary object placed in a known environment with a combination of GRASP and VND ⋮ Solving the clustered traveling salesman problem with ‐relaxed priority rule ⋮ Improving a state‐of‐the‐art heuristic for the minimum latency problem with data mining ⋮ Hybrid evolutionary search for the traveling repairman problem with profits ⋮ Minimizing latency in post-disaster road clearance operations ⋮ Minimizing customers' waiting time in a vehicle routing problem with unit demands ⋮ Weighted online minimum latency problem with edge uncertainty ⋮ A truck and drones model for last-mile delivery: a mathematical model and heuristic approach ⋮ The demand weighted vehicle routing problem ⋮ An adaptive large neighborhood search approach for multiple traveling repairman problem with profits ⋮ A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem ⋮ A unified solution framework for multi-attribute vehicle routing problems ⋮ A hybrid reactive GRASP heuristic for the risk-averse \(k\)-traveling repairman problem with profits ⋮ A metaheuristic for the delivery man problem with time windows ⋮ Integer programming formulations and efficient local search for relaxed correlation clustering ⋮ An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems ⋮ A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem ⋮ Solving the traveling delivery person problem with limited computational time

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The delivery man problem with time windows
• Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem
• Exact algorithms for the minimum latency problem
• The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times
• An effective memetic algorithm for the cumulative capacitated vehicle routing problem
• A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery
• A new formulation for the traveling deliveryman problem
• An improved approximation ratio for the minimum latency problem
• Variable neighborhood search
• A classification of formulations for the (time-dependent) traveling salesman problem
• An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem
• Greedy randomized adaptive search procedures
• The time dependent traveling salesman problem: polyhedra and algorithm
• The minimum latency problem
• Heuristics for the Traveling Repairman Problem with Profits
• The Directed Minimum Latency Problem
• Special cases of traveling salesman and repairman problems with time windows
• TSPLIB—A Traveling Salesman Problem Library
• P-Complete Approximation Problems
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• The Delivery Man Problem and Cumulative Matroids
• Approximation Schemes for Minimum Latency Problems
• Time‐dependent traveling salesman problem–the deliveryman case
• A note on the traveling repairman problem
• The k -traveling repairmen problem
• The traveling salesman problem with cumulative costs

This page was built for publication: A simple and effective metaheuristic for the minimum latency problem