RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., 2014, Volume 21, Number 4, Pages 42–53 (Mi da784)  

Probabilistic analysis of one routing problem

A. M. Istominab

a Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia
b S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia

Abstract: We consider the unit-demand Euclidean vehicle routing problem (VRP), where $n$ customers are modeled as independent identically distributed points on the plane and have unit demand. The Iterated Tour Partitioning heuristic (ITP) for VRP is known. The ITP heuristic is a $2$-approximation algorithm in a general case. But if customers are modeled as i.i.d. points with uniform distribution on the unit square, then it is shown that ITP is a $(2-c)$-approximation algorithm ($c>0$). In the paper, the same result is proved in the case when customers are i.i.d. points with uniform distribution on the circle of the unit area. Ill. 3, bibliogr. 7.

Keywords: vehicle routing problem, approximation algorithm, probabilistic analysis, guarantee approximation ratio.

Full text: PDF file (305 kB)
References: PDF file   HTML file

Bibliographic databases:
UDC: 519.8
Received: 13.12.2011
Revised: 13.02.2014

Citation: A. M. Istomin, “Probabilistic analysis of one routing problem”, Diskretn. Anal. Issled. Oper., 21:4 (2014), 42–53

Citation in format AMSBIB
\Bibitem{Ist14}
\by A.~M.~Istomin
\paper Probabilistic analysis of one routing problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2014
\vol 21
\issue 4
\pages 42--53
\mathnet{http://mi.mathnet.ru/da784}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3289220}


Linking options:
  • http://mi.mathnet.ru/eng/da784
  • http://mi.mathnet.ru/eng/da/v21/i4/p42

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Number of views:
    This page:136
    Full text:49
    References:37
    First page:14

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020