zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. (English) Zbl 1179.90068

Summary: This paper proposes a formulation of the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) and a particle swarm optimization (PSO) algorithm for solving it. The formulation is a generalization of three existing VRPSPD formulations. The main PSO algorithm is developed based on GLNPSO, a PSO algorithm with multiple social structures. A random key-based solution representation and decoding method is proposed for implementing PSO for VRPSPD. The solution representation for VRPSPD with n customers and m vehicles is a (n+2m)-dimensional particle. The decoding method starts by transforming the particle to a priority list of customers to enter the route and a priority matrix of vehicles to serve each customer. The vehicle routes are constructed based on the customer priority list and vehicle priority matrix. The proposed algorithm is tested using three benchmark data sets available from the literature. The computational result shows that the proposed method is competitive with other published results for solving VRPSPD. Some new best known solutions of the benchmark problem are also found by the proposed method.

Scope and Purpose

This paper applies a real-value version of particle swarm optimization (PSO) algorithm for solving the vehicle routing problem with simultaneous pickup and delivery (VRPSPD). The VRPSPD formulation is reformulated and generalized from three existing formulations in the literature. The purposes of this paper are to explain the mechanism of the PSO for solving VRPSPD and to demonstrate the effectiveness of the proposed method.

MSC:
90B20Traffic problems
References:
[1]Christofides, N.; Mingozzi, A.; Toth, P.: The vehicle routing problem, Combinatorial optimization, 315-338 (1979) · Zbl 0413.90075
[2], The vehicle routing problem (2002)
[3]Min, H.: The multiple vehicle routing problem with simultaneous delivery and Pick-up points, Transportation research A 23, No. 5, 377-386 (1989)
[4]Dethloff, J.: Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and Pick-up, OR spektrum 23, No. 1, 79-96 (2001) · Zbl 1015.90022 · doi:10.1007/PL00013346
[5]Salhi, S.; Nagy, G.: A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the operational research society 50, No. 10, 1034-1042 (1999) · Zbl 1054.90523
[6]Nagy, G.; Salhi, S.: Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European journal of operational research 162, No. 1, 126-141 (2005) · Zbl 1132.90380 · doi:10.1016/j.ejor.2002.11.003
[7]Tang, F. A.; Galvao, R. D.: A tabu search algorithm for the vehicle routing problem with simultaneous Pick-up and delivery service, Computers and operations research 33, No. 3, 595-619 (2006) · Zbl 1077.90058 · doi:10.1016/j.cor.2004.07.009
[8]Bianchessi, N.; Righini, G.: Heuristic algorithms for the vehicle routing problem with simultaneous Pick-up and delivery, Computers and operations research 34, No. 2, 578-594 (2007) · Zbl 1109.90016 · doi:10.1016/j.cor.2005.03.014
[9]Dell’amico, M.; Righini, G.; Salani, M.: A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection, Transportation science 40, No. 2, 235-247 (2006)
[10]Berbeglia, G.; Cordeau, J. F.; Gribkovskaia, I.; Laporte, G.: Static pickup and delivery problems: a classification scheme and survey, Top 15, No. 1, 1-31 (2007) · Zbl 1121.90001 · doi:10.1007/s11750-007-0009-0
[11]Kennedy, J.; Eberhart, R.: Particle swarm optimization, Proceedings of IEEE international conference on neural networks 4, 1942-1948 (1995)
[12]Kennedy, J.; Eberhart, R. C.: Swarm intelligence, (2001)
[13]Clerc, M.: Particle swarm optimization, (2006)
[14]Baker, B. M.; Ayechew, M. A.: A genetic algorithm for the vehicle routing problem, Computers and operations research 30, No. 5, 787-800 (2003) · Zbl 1026.90013 · doi:10.1016/S0305-0548(02)00051-5
[15]Berger, J.; Barkaoui, M.: A parallel hybrid genetic algorithm for the vehicle routing problem with time windows, Computers and operations research 31, No. 12, 2037-2053 (2004) · Zbl 1100.90503 · doi:10.1016/S0305-0548(03)00163-1
[16]Thangiah, S. R.; Salhi, S.: Genetic clustering: an adaptive heuristic for the multidepot vehicle routing problem, Applied artificial intelligence 15, No. 4, 361-383 (2001)
[17]Bullnheimer, R.; Hartl, F.; Strauss, C.: An improved ant system algorithm for the vehicle routing problem, Annals of operations research 89, 319-328 (1999) · Zbl 0937.90125 · doi:10.1023/A:1018940026670
[18]Reimann, M.; Doerner, K.; Hartl, R. F.: D-ants: savings based ants divide and conquer the vehicle routing problem, Computers and operations research 31, No. 4, 563-591 (2004) · Zbl 1061.90024 · doi:10.1016/S0305-0548(03)00014-5
[19]Chen, A. L.; Yang, G. K.; Wu, Z. M.: Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem, Journal of zhejiang university science A 7, No. 4, 607-614 (2006) · Zbl 1166.90319 · doi:10.1631/jzus.2006.A0607
[20]Pongchairerks, P.; Kachitvichyanukul, V.: A non-homogenous particle swarm optimization with multiple social structures, , A5-02 (2005)
[21]Veeramachaneni, K.; Peram, T.; Mohan, C.; Osadciw, L. A.: Optimization using particle swarms with near neighbor interaction, , 110-121 (2003) · Zbl 1028.68918 · doi:http://link.springer.de/link/service/series/0558/bibs/2723/27230110.htm