The probabilistic uncapacitated open vehicle routing location problem

Suppose that m$$ m $$ mobile service units are located at a base station (depot) in a transportation network with n$$ n $$ nodes. On any day, the nodes of the network may generate calls for service independently with known probabilities. The calls are centrally allocated to the service units who then visit the allocated customers on shortest open tours, that is, for each service unit, the way back to the depot from the last served customer is not counted towards the length of the tour. It is required to find an optimal location for the depot to minimize the expected travel distance. We obtain bounds on the approximation ratios for two simple and fast heuristics for the problem on a general network. For the problem on a tree, we present an O(nm+1)$$ O\left({n}^{m+1}\right) $$ exact algorithm.

• Publication year

  2023

• Venue

  Networks

• Publication date

  2023-04-06

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1002/net.22147
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The open vehicle routing problem with decoupling points

  2018cited by this paper
• 50th Anniversary Invited Article - Future Research Directions in Stochastic Vehicle Routing

  2016influential reference
• The offshore wind farm array cable layout problem: a planar open vehicle routing problem

  2015cited by this paper
• An improved formulation for the multi-depot open vehicle routing problem

  2015cited by this paper
• A survey of recent research on location-routing problems

  2014influential reference
• A multi-start algorithm for a balanced real-world Open Vehicle Routing Problem

  2014cited by this paper
• A taxonomical analysis, current methods and objectives on location-routing problems

  2013cited by this paper
• Technical Note - Approximation Algorithms for VRP with Stochastic Demands

  2012cited by this paper
• Approximation Algorithms for VRP with Stochastic Demands

  2012influential reference
• A hybrid evolution strategy for the open vehicle routing problem

  2010cited by this paper
• A variable neighbourhood search algorithm for the open vehicle routing problem

  2009influential reference
• An ILP improvement procedure for the Open Vehicle Routing Problem

  2008cited by this paper
• The open vehicle routing problem: Algorithms, large-scale test problems, and computational results

  2007cited by this paper
• Vehicle routing with stochastic demands: Models & computational methods

  2002cited by this paper
• Modeling uncertainty : an examination of stochastic theory, methods, and applications

  2002cited by this paper
• Probabilistic Sales-Delivery Man and Sales-Delivery Facility Location Problems on a Tree

  1995cited by this paper
• Probabilistic a priori routing‐location problems

  1994cited by this paper
• Traveling Salesman Facility Location Problems

  1989influential reference
• A Heuristic Algorithm for the Traveling Salesman Location Problem on Networks

  1988influential reference
• Minisum location of a traveling salesman

  1986influential reference
• TRAVELING SALESMAN LOCATION PROBLEM

  1976cited by this paper

• The Optimization Model and Algorithm of Emergency Logistics Vehicle Routing Problem Considering Random Demand and Robustness

  2025cites this paper