Open access

Complexity of Instances for Combinatorial Optimization Problems

Written By

Jorge A. Ruiz-Vanoye, Ocotlan Diaz-Parra, Joaquin Perez-Ortega, Rodolfo A. Pazos R., Gerardo Reyes Salgado and Juan Javier Gonzalez-Barbosa

Published: 01 February 2010

DOI: 10.5772/7807

From the Edited Volume

Computational Intelligence and Modern Heuristics

Edited by Al-Dahoud Ali

Chapter metrics overview

2,364 Chapter Downloads

View Full Metrics

1. Introduction

The theory of the computational complexity is the part of the theory of the computation that studies the resources required during the calculation to solve a problem (Cook, 1983). The resources commonly studied are the time (execution number of an algorithm to solve a problem) and the space (amount of resources to solve a problem). In this area exist problems classifications that are approached within the theory of the complexity, some definitions of the complexity classes are related to this investigation:

  1. P class.-It is the class of recognizable languages by a determinist Turing Machine of one tape in polynomial time (Karp, 1972).

  2. NP class.-It is the class of recognizable languages by a Non-determinist Turing Machine of one tape in polynomial time (Karp, 1972).

  3. NP-equivalent class.-It is the class of problems that are considered NP-easy and NP-hard (Jonsson & Bäckström, 1995).

  4. NP-easy class.-It is the class of problems that are recognizable in polynomial time by a Turing Machine with one Oracle (subroutine). In other words a problem X is NP-easy if and only if a Y problem exists in NP like X is reducible Turing in polynomial (Jonsson & Bäckström, 1995).

  5. NP-hard class.-A Q problem is NP-hard if each problem in NP is reducible to Q (Garey & Johnson, 1979; Papadimitriou & Steiglitz, 1982). It is the class of problems classified as problems of combinatorial optimization at least as complex as NP.

  6. NP-complete class.-A L language is NP-complete if L is in NP, and Satisfiability ≤p L (Cormen et al., 2001; Karp, 1972; Cook, 1971). It is the class of problems classified like decision problems.

A combinatorial optimization problem is either a minimization problem or a maximization problem and consists of three parts: a) a set of instances, b) candidate solutions for each instance, c) a solution value (Garey & Johnson, 1979). The combinatorial optimization problems that was used in this paper: the General Asymmetric Traveling Salesman Problem (ATSP), JobShop Scheduling Problem (JSSP) and Vehicle Routing Problem with Time Windows (VRPTW).

The general Asymmetric Traveling Salesman Problem (ATSP), which can be stated as follows: given a set of nodes and distances for each pair of nodes, find a route of minimal overall length that visits each of the nodes exactly once (Cormen et al., 2001). The distance of node i to node j and the distance of node j to node i can be different (Equation 1, 2, 3, 4).

minz(x)=j=1mi=1mdijxijE1
j=1mxij=1;     i=1,...,m;       dijdjiE2
i=1mxij=1;     j=1,...,m ;           0xij1E3
xij={0,if tour traverses from i to j1,otherwise                             i,jE4

The JobShop Scheduling Problem (JSSP) contains a number of machines and a set of Jobs each one with precedence restrictions, the problem is to solve the question if exist a scheduling of jobs that help to improve and to efficiency the use of the machines being eliminated the idle times. It is recognized by that it does not have to be able human nor machine sufficiently fast that it can obtain the optimal solution for JSSP due to the solutions space, which cannot be expressed by a polynomial function (deterministic algorithm), the space of solutions for this kind of problem can be only expressed like an exponential function. For the problem of JSSP is necessary to diminish makespan (cmax), this can be formulated as it follows (Equation 5, 6, 7, 8):

min cmaxE5
cjKtjkcjh, j=1,2,...,n  h,k=1,2,...,mE6
cjKcik+M(1xijk)tjk,  i,j=1,2,...n     k=1,2,...,mE7
ciK,cjK0, xijk=1 or 0i=1,2,...,n    k=1,2,...,mE8

The Vehicle Routing Problem with Time Windows (VRPTW) is a combinatorial optimization problem complex (Toth & Vigo, 2001; Ruiz-Vanoye et al., 2008b; Cruz-Chávez et al., 2008). The VRPTW (Toth & Vigo, 2001) consists basically of to minimize the costs of subject transportation to time restrictions of each route and capacity on the cradle of the demand of each client (Equation 9 and 10).

min kK(i,j)AcijxijkE9
aij+(i)xijkwikbij+(i)xijk,kK,iNE10

In this paper, we propose specify the complexity of instances for problems of combinatorial optimization (ATSP, VRPTW, and JSSP).

Advertisement

2. Related works

An important measurement of complexity that we can attribute to Shannon (1949), is the complexity of Boolean circuits. For this measurement he is advisable to assume that f function at issue transforms finite strings of bits into finite strings of bits, and the complexity of f is the size of the smaller Boolean circuit than it calculates f for all the inputs of n length. But, it does not exist a classification of the complexity of instances for combinatorial optimization problems.

In some combinatorial optimization problems exists diverse types of instances size at the moment, for example:

REINELT (Reinelt, 1991) mentions that in General Asymmetric Traveling Salesman Problem (ATSP) instances exist whose size based on the number of cities or nc. See Table 1.

YAMADA (Yamada & Nakano, 1997) mentions that for the problem JobShop Scheduling Problem (JSSP) the size of the problem is the number of jobs or J and the number of machines or M. See Table 2.

SOLOMON (Solomon, 1987; Toth & Vigo, 2001) mentions that in the problem Vehicle Routing Problem with Time Windows (VRPTW) exists classifications of type C for instances clustered, type RC for instances Random and Clustered, Type R for Random instances and in addition the instance is determining by the number of clients or CN. See Table 3.

I nstancesn c
br1717
ft5353
ft7070
ftv3333
ftv3535
ftv3838
ftv5555
ftv6464
ftv7070
ftv170170
rbg443443
ry48p48

Table 1.

Number of cities for ATSP instances.

I nstancesJ*M
abz510x10
abz610x10
abz820x15
ft066x6
ft1010x10
ft2020x5
orb0110x10
orb0210x10
yn120x20
yn220x20
yn320x20
yn420x20

Table 2.

Number of jobs and number of machines for JSSP instances.

I nstancesCN
25
225
c20525
r10150
r10250
r201100
r205100
rc101200
rc102200
rc201500
rc202500
rc203500
rc204500
rc205500

Table 3.

Client number for VRPTW instances.

Advertisement

3. Complexity of Instances for Combinatorial Optimization Problems

In this section, we propose a basic methodology (Figure 1) for create the metric that permit to classify or to determine the complexity instances of combinatorial optimization problems.

Step 1. To identify the maximum instance solved of the problem.

Step 2. To identify the instances parameters of the problem.

Step 3. Elaboration of the general metric of instances complexity taking into account measured of descriptive statistics and the parameters of the problems (Equation 11).

InstancesComplexity= (PS+AM+SD+GD+RA)/100E11

Where: PS is the instance average size at the rate of the instance maximum solved of the problem, AM is the sum of the arithmetic mean of each instance parameters (that have several elements), SD is the sum of the standard deviations of each type of parameter (that have several elements), GD is the sum of the genetic distances which quantifies the similarity or differentiates between the populations from the frequencies of the elements from each parameters (that have several elements) of the problem, RA is the sum of the existing reasons between the greatest value and the value smaller of each parameter (that has several elements) of the problem.

Figure 1.

Methodology of complexity instances for computational combinatorial problems.

Advertisement

4. Experimentation

The experimentation was performed on a computer with Celeron processor 1.5GHz, 512 MB of memory, 80 GB of hard disk.

We use: the ATSP instances obtained of TSPLIB (Reinelt, 1991) benchmark, the JSSP instances of JSSPLIB (Yamada & Nakano, 1997) benchmark, the VRPTW instances of Solomon (Solomon, 1987) benchmark, and a genetic algorithm from Heuristics Lab (Wagner & Affenzeller, 2004) software.

A genetic algorithm (GA) is one of the heuristic methods used to find approximate solutions to NP-complete problems, GA is inspired by the Darwinian principles of the evolution of the species, and use own techniques of the genetics, such as: inheritance, mutation, natural selection and recombination (or crossover). The simplest form of genetic algorithm involves three types of operators: selection, crossover (single point), and mutation (Holland, 1975; Mitchell, 1998). Selection, this operator selects chromosomes in the population for reproduction. The fitter the chromosome, the more times it is likely to be selected to reproduce. Crossover, this operator randomly chooses a locus and exchanges the subsequences before and after that locus between two chromosomes to create two offspring. The crossover operator roughly mimics biological recombination between two single-chromosome organisms. Mutation, this operator randomly flips some of the bits in a chromosome. Mutation can occur at each bit position in a string with some probability. The genetic algorithm (Wagner & Affenzeller, 2004) was used to verify the time and the quality of instances solution with the purpose of determining if the metric generated classify in complexity terms. The input parameters were: selection operator = Roulette, crossover operator = OX, mutation operator = Simple Inversion, generations = 1000, population size = 100, mutation rate = 0.05, replacement strategy = Elitism, crossover rate = 1, n-Elitism = 1, tournament group size = 2.

4.1. Experimentation in ATSP

Using the process contained in the general methodology to ATSP, the steps they would be of the following way:

Step 1. The maximum instance solved for ATSP is of 1.904.711 cities or World TSP (Applegate et al., 2006).

Step 2. The instances parameters of general ATSP can be codified in a hypothetical language: L = “nc, d1, d2, …, dz”. In other words two general parameters nc = number of cities and dz =distances between the cities.

Step 3. Elaboration of the instances complexity metric for ATSP. In order to create the complexity general metric, for which it is necessary to determine PS (Equation 12), AM (Equation 13), SD (Equation 14), GD (Equation 15), RA (Equation 16) indicators.

PS=ncncmaxE12

Where: PS is the average size of the instance at the rate of the instance maximum solved of ATSP, nc is the value of the problem to solve and ncmax is the size of greater instance solved.

AM=i=1ndincE13

Where: AM is the sum of the arithmetic mean of each parameter (that has several elements) of the instance, di are the elements of the parameter that has several elements called matrix of cities and nc is the number of cities.

SD=(i=1n(AM(dinc)))2E14

Where: SD is the sum of the standard deviations of each type of parameter (that has several elements), di = Value of distances between cities i, nc = number of cities, AM = index of the arithmetic mean of distances.

GD={Frequency(di)>1, if Frequency(di)>1 for some i0, otherwiseE15

Where: GD is the sum of the genetic distances which quantifies the similarity or differentiates between the populations from the frequencies of the elements from each parameter of the problem.

RA=mindimaxdiE16

Where: RA is the sum of the existing reasons between the greatest value and the smallest value of each parameter (that has several elements) of the NP-hard problem, min di = minimal distance between cities, max di = value of maximum distances between cities.

In Table 4 are the results of applying the instances complexity metric (IC) on ATSP instances, in addition to the summary of the obtained result to execute algorithm GA with the ATSP instances.

I nstancesncG A d tPS AMSDRAGDI C
br171700.790.00000812.1218.450.160.530.31
ft535345.21.720.000027283.15377.020.150.326.60
ft707028.83.680.000036721.74434.820.270.2411.57
ftv3333423.210.00001788.4761.930.260.221.50
ftv353526.63.220.000018139.0764.330.410.362.04
ftv383838.13.090.00001968.1462.520.200.261.31
ftv444456.33.170.00002370.1863.310.210.301.34
ftv474743.83.090.000024145.4065.450.410.482.11
ftv555594.03.160.00002888.9961.520.280.561.51
ftv646475.92.910.00003321.8368.260.060.650.90
ftv707088.13.610.00003622.3969.100.070.710.92
ftv1701703253.910.00008977.1869.300.211.701.48
rbg4434431246.330.0002321.778.270.03894.009.04
ry48p4810673.040.000025264.11578.730.960.128.43

Table 4.

Results obtained from descriptive statistical measures with the ATSP instances.

Where: d is the difference between best know and the obtained solution, t is the solution time for the instance on the GA algorithm. In the instance complexity (IC) between ft70 and ftv70 instances exist different values for instances with equal number of cities (nc), indicates that the ft70 instance is more complex than ftv70 instance and is verified with the obtained solution to apply the GA algorithm to the instances. In addition to being able to compare between the ftv70 and ftv64 instances, the ftv70 instance is more complex than ftv64 instance.

4.2. Experimentation in JSSP

Using the methodology with problem JSSP, are the following steps:

Step 1. The maximum instance resolved is of 20 by 20 symmetrical (Yamada & Nakano, 1997).

Step 2. The parameters of the instances of the JSSP can be codified in a hypothetical language: L = “nj, nm, J1(m0, pt0,…..mnm-1, ptnm-1),…, Jnj (m0, pt0,..., mnm-1, ptnm-1). Where nj = Number of jobs, nm = number of machines, J = Jobs, m = machine and pt = processing time.

Step 3. Elaboration of the complexity metric for JSSP. In order to create the complexity general metric is used the Equation 1, for which it is necessary to determine PS (Equation 17), AM (Equation 18), SD (Equation 19), DG (Equation 20), RA (Equation 21) indicators.

PS=(nj*nmMAXJSSP)E17

Where: PS is the so large average of the instance at the rate of the maximum instance from problem JSSP. And MAXJSSP = the maximum instance solved in literature or MAX(nj ∗ nm).

AM=i=1zmim(nj*nm)+i=1zptipt(nj*nm)E18

Where the AM metric is the sum of the arithmetic mean of the m, pt parameters.

SD=(i=1n(AMm(mim(nj*nm))))2+(i=1n(AMpt(ptipt(nj*nm))))2E19

Where the SD metric contains the sum of the standard deviations of the m, pt, J parameters. And MA is the arithmetic mean of m parameter; MApt is the arithmetic mean of pt parameter.

GD=[Frequency(m)+Frequency(pt)]/100E20

Where the GD metric contains the genetic distances between the populations by the frequencies of the parameters (m, pt).

RA=MIN mMAX m+MIN ptMAX ptE21

Where the RA metric contains the sum of the reasons between the minimal and maximuml values of the m and pt parameters.

The Table 5 contains the results of applied the complexity metric for JSSP, and the results of the GA on JSSP instances. This can be observed that in the Instance Complexity (IC) between la01 and la05 instances exist different values with equal Number of Jobs and Number of Machines, indicates that the la01 instance is more complex than the la05 instance is verified with the quality of the obtained solution. Also sample that in between the yn1 and yn4 instances, the yn4 instance is more complex that yn1 instance. Where: d is the difference between best know and the obtained solution, t is the solution time for the instance on the GA algorithm.

I nstancesJ*MGA d tTPMADARADGI C
abz510x104.290:55.30.2573.642302 . 6 90.5050.1023.77
abz610x103.391:09.30.2558.511830 . 020.2040.1018.89
abz820x1516.62:00.80.7529.122247.370.2750.2022.77
abz920x1514.31:46.50.7529.281862 . 310.2750.0218.92
ft066x600:08.50.097.25156.570.1 000.061.64
ft1010x108.060:28.40.2551.641615.420.0200.1016.67
ft2020x53.430:35.30.2551.162280.330.02 00. 2023.31
la0110x500:13.70.1253.821177.070.1220.1012.31
la0210x50.150:15.20.1250.241098.870.1210.1011.49
la0310x54.350:04.30.1244.22966.580.0760.1010.11
la0410x52.030:14.50.1246.221010.190.0510.1010.56
la0510x500:13.50.1240.06874.450.0510.109.14
la0615x500:22.30.1851.781730.970.0710.1017.83
la0715x500:25.40.1848.131608.840.0820.1016.57
la0815x500:25.90.1849.051639 . 640.0510.1016.88
la0915x500:24.60.1854.621825.9 10.0 700.1018. 8 0
la1015x500:23.10.1853.281781.120.0510.1018.34
orb0110x105.000:28.70.2553.361668.860.0500.1017.22
orb0210x105.960:23.40.2550.911591.870.0600.1016. 4 3
orb0310x109.650:24.40.2552.791651 . 210.0500.1017 . 04
yn120x200.781:15.81.0036.123217 . 550.2040.2 532.55
yn220x202.781:18.11.0036.233227.610.2040.2 632.65
yn320x202.071:19.01.0032. 073169.990.2040. 2732.07
yn420x200.801:25.81.0036.843281. 540.2040.3133.19

Table 5.

Results obtained by the descriptive statistics with the JSSP instances.

4.3. Experimentation in VRPTW

Using the methodology with VRPTW, the following steps are obtained:

Step 1. The maximum instance solved of problem VRP is F-n135-k7, with VN = 12, C = 2210, CN = 135 (Toth & Vigo, 2001).

Step 2. The parameters of the instances of problem VRPTW can be codified in a hypothetical language: L = “VN, C, (CN1, XCO1, YCO1, D1, RT1, DT1, ST1, …, CNz, XCOz, YCOz, Dz, RTz, DTz, STz)”. Where VN = Vehicle Number, C = Capacity, CN = Customer Number, XCO = X Coord., YCO = Y Coord., D = Demand, RT = Ready Time, DT = Due date, ST = Service Time.

Step 3: Elaboration of the complexity metric for problem VRPTW. In order to create the complexity general metric the Equation 1 is used, for which it is necessary to determine PS (Equation 22), AM (Equation 23), SD (Equation 24), GD (Equation 25), RA (Equation 26) indicators.

PS=VN*C*CNnVRPTWMAX, VRPTWMAX=MAX(VN*C*CNn)E22

Where: PS = is the problem size of the instance at the rate of the maximum instance solved from VRPTW, max(VN * C * CNn) = the value of the maximum instance solved by literature.

AM=i=1nXCOiCNz+i=1nYCOiCNz+i=1nDiCNz+i=1nRTiCNz+i=1nDTiCNz+i=1nSTiCNzE23

Where: In AM contains the sum of the arithmetic mean of the XCO, YCO, D, RT, DT y ST parameters.

SD=(i=1n(AMXCO(XCOiCNz)))2+(i=1n(AMYCO(YCOiCNz)))2+        (i=1n(AMD(DiCNz)))2+ (i=1n(AMRT(RTiCNz)))2+       (i=1n(AMDT(DTiCNz)))2+(i=1n(AMST(STiCNz)))2E24

Where: SD contains the sum of the standard deviations of the XCO, YCO, D, RT, DT y ST parameters. AMXCO is the arithmetic mean of XCO parameter, AMYCO is the arithmetic mean of YCO parameter, AMD is the arithmetic mean of D parameter, AMRT is the arithmetic mean of RT parameter, AMDT is the arithmetic mean of DT parameter, and AMST is the arithmetic mean of ST parameter.

GD=[Frequency(XCO)+Frequency(YCO)+          Frequency(D)+Frequency(RT)+          Frequency(DT)+Frequency(ST)]/100E25

Where: GD contains the genetic distances between populations from the frequencies of each parameter (XCO, YCO, D, RT, DT y ST).

RA=(MIN XCOMAX XCO)+(MIN YCOMAX YCO)+        (MIN DMAX D)+(MIN RTMAX RT)+       (MIN DTMAX DT)+(MIN STMAX ST)E26

Where RA contains the sum of the reasons between the minimal and maximuml values of the XCO, YCO, D, RT, DT y ST parameters.

In Table 6 are the results of applying the complexity metric on VRPTW instances, in addition to the summary of the obtained result to execute algorithm GA with the VRPTW instances. Where: d is the difference between best know and the obtained solution, t is the solution time for the instance on the GA algorithm, VN = Vehicle Number, C = Capacity, CN = Customer Number. It can be observer that in the Instance Complexity (IC) between c204 and c201 different values for instances with equal Vehicle Number Capacity and Customer Number exist, this indicates that the instance c204 is more complex than c201 and is verified with the obtained solution to apply GA to the instances.

It is necessary to mention that the values of complexity of the instances of single VRPTW are comparable between instances of the same problem.

I nstancesVNCCNG A d tTPMADARADGI C
252002500:580.0341143.92285981.0170.10297.43
225200250.051:030.0341158.68289671.0220.17301.26
3252002501:000.0341284.92321231.0370.23334.09
252002501:010.0341303.68325921.0370.27338.97
5252002501:260.0341151.12287781.0600.10299.30
c2012510002501:350.1223657.96914490.8940.08951.08
c202257002501:340.1223898.96974740.8940.151013.74
c203257002502:030.1224032.081008020.8970.211048.35
c20425700250.11:480.1224081.201020301.2630.251061.12
c205257002501:440.1223675.56918890.9410.08955.65
r10125200250.061:400.034310.3677590.4310.0980.69
r10225200251.371:110.034318.4479610.4310.1682.80
r10325200251.121:190.034317.9679490.5580.2282.67
r10425200250.161:540.034309.5677390.5580.2680.49
r10525200252.151:200.034310.6877670.4840.0980.78
r20125700251.191:490.1741058.32264580.4580.09275.17
r20225700250.392:090.1741122.44280610.4920.16291.84
r20325700250.832:050.1741146.04286510.5490.22297.97
r20425700252.662:040.1741114.84278710.5490.26289.86
r205257002502:000.1741057.80264450.5090.09275.03
rc101257002501:220.034326.7281680.3290.0884.95
rc102257002501:170.034327.7281930.3290.1585.21
rc103257002502:090.034323.3680840.4250.2184.08
rc10425700250.111:270.034313.2878320.4250.2581.45
rc10525700250.441:150.034335.0483760.3830.0887.11
rc201257002501:420.1741024.00256000.2200.08266.24
rc202257002502:030.1741077.24269310.2200.15280.08
rc20325700250.32:380.1741099.20274800.3650.21285.79
rc204257002502:070.1741067.52266880.3650.25277.56
rc205257002502:140.1741044.88261220.3330.08271.67

Table 6.

Results obtained by metrics descriptive statistics with VRPTW instances.

Advertisement

5. Conclusions

We can conclude that the creation of a mathematical expression based on the descriptive statistics able is possible to measure the complexity the instances of combinatorial optimization problems, in this paper was demonstrated for ATSP, VRPTW and JSSP. It is necessary to mention that, the values of instances complexity of ATSP, VRPTW and JSSP problems are only comparable between instances of the same problem.

The intention of this paper was to classify the complexity of the instances and not therefore the complexity between problems NP, as future works, we propose to validate the methodology for other NPs problems.

References

  1. 1. ApplegateD. L.BixbyR. E.ChvátalY.CookW. J. 2006 The Traveling Salesman Problem: A Computational Study, Princeton University Press, 0-69112-993-2 Jersey
  2. 2. BlantonJ. L.WainwrightR. L. 1993 Multiple Vehicle Routing with Time and Capacity Constrainst using Genetic Algorithms, Proceedings of the Fifth International Conference on Genetic Algorithms, 452459 , 1-55860-299-2 Mateo, CA, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA
  3. 3. ChakrabortyaU. K. 2008 Including Special Section: Genetic and Evolutionary Computing, Information Sciences, 178 N. 23, 4419-4420, 0020-0255
  4. 4. ChenC. L.BulfinR. L. 17 N. 1, 1-7, 0305-0548.
  5. 5. CookS. A. 1971 The Complexity of Theorem Proving Procedures, Proceedings of 3rd ACM Symposium on Theory of Computing, 151158 , Shaker Heights, Ohio, United States, May 03-05, 1971, ACM, New York, NY, USA
  6. 6. CookS. A. 1983 An Overview of Computational Complexity. Communications of the ACM, 26 6 (June 1983) 400408 , 0001-0782
  7. 7. CormenH. T.LeisersonC. E.RivestR. L.SteinC. 2001 Introduction to Algorithms, MIT Press, 0-26203-293-7 Massachusetts London, England
  8. 8. Cruz-ChávezM. A.Díaz-ParraO.Juárez-RomeroD.Martínez-RangelM. G. 2008 Memetic Algorithm Based on a Constraint Satisfaction Technique for VRPTW, In: Artificial Intelligence and Soft Computing- ICAISC 2008, 5097 Rutkowski, N L. et al. (Eds.), 376387 , Springer-Verlag, 978-3-54069-572-1
  9. 9. GareyM. R.JohnsonD. S. 1979 Computers and Intractability, a Guide to the Theory of NP-completeness, W. H. Freeman and Company, 0-71671-044-7 York
  10. 10. GładyszB. 2007 Fuzzy robust courses scheduling problem, Fuzzy Optimization and Decision Making, 6 N. 2, 155-161, 1568-4539
  11. 11. DahalK. P.HossainA.VargheseB.AbrahamA.XhafaF.DaradoumisA. 2008 Scheduling in Multiprocessor System Using Genetic Algorithms, 7th International Conference on Computer Information Systems and Industrial Management Applications (CISIM’08), 277282 , 978-0-76953-184-7 2008, IEEE Computer Society press, USA.
  12. 12. HollandJ. H. 123 1975 Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor
  13. 13. JainL. C.TanS. C.LimC. P. 2008 An Introduction to Computational Intelligence Paradigms. In: Computational Intelligence Paradigms, 137 Studies in Computational Intelligence. Lakhmi C. Jain et al. (Eds.), 1-23, Springer-Verlag. 978-3-54079-473-8
  14. 14. JonssonP.BäckströmC. 1995 Complexity Results for State-Variable Planning under Mixed Syntactical and Structural Restrictions, Proceedings of the sixth international conference on Artificial intelligence: methodology, systems, applications, 205213 , 981-02-1877-X Smolenice Castle, Slovakia, 1994, World Scientific Publishing Co., Inc. River Edge, NJ, USA
  15. 15. KarpR. M. 1972 Reducibility Among Combinatorial Problems, In: Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, (Ed.), 85104 , Springer, 0-30630-707-3
  16. 16. LimC. P.JainL. C.NguyenN. T.BalasV. E. 2008 Guest Editorial: Special issue on advances in computational intelligence paradigms and applications, Fuzzy Optimization and Decision Making. 7 N. 3, 215217 , 1568-4539
  17. 17. McCabeT. J. 1976 A complexity measure, Transactions on Software Engineering, 2 N.4, (July 1976) 308320 , 0098-5589
  18. 18. MitchellM. 1998 An Introduction to genetic algorithms, MIT Press, 0-26213-316-4 London, England
  19. 19. PapadimitriouC.SteiglitzK. 1982 Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 0-20153-082-1 Jersey
  20. 20. PérezJ.PazosR. A.FraustoJ.RodríguezG.RomeroD.CruzL. 2004 A Statistical Approach for Algorithm Selection, Proceedings of III International Workshop on Experimental an Efficient Algorithms, 417431 , 3-54022-067-4 Angra dos Reis, Brazil, May 25-28, 2004, Springer-Verlag, Berlin
  21. 21. ReineltG. 1991 TSPLIB- A Traveling Salesman Problem Library. ORSA Journal on Computing, 3 N. 4, 376-384, 0899-1499
  22. 22. Ruiz-VanoyeJ. A.Díaz-ParraO.LanderoV. 2008 A Metric to Discriminate the Selection of Algorithms for General Problem ATSP, In: Knowledge-Based Intelligent Information and Engineering Systems- KES 2008, 5177 I. Lovrek, R.J. Howlett, and L.C. Jain (Eds.), 106-113, Springer-Verlag, 978-3-54085-562-0 Berlin
  23. 23. Ruiz-VanoyeJ. A.ZárateJ. A.Díaz-ParraO.LanderoV. 2008 Applied Statistical Indicators to the Vehicle Routing Problem with Time Windows for Discriminate Appropriately the Best Algorithm, In: Computational Science and Its Applications- ICCSA 2008, 5073 Part II, O. Gervasi et al. (Eds.), 11311141 , Springer-Verlag, 978-3-54069-840-1 Berlin
  24. 24. ShannonC. E.WeaverW. 1949 The Mathematical Theory of Communication, University of Illinois Press, ASIN: B000UFWID2, Urbana, Illinois
  25. 25. SolomonM. M. 1987 Algorithms for Vehicle Routing and Scheduling Problems with Time Window Constrains. Operations Research, 35 2 March-April 1987) 254-265, 0030-364X
  26. 26. TothP.VigoD. 2001 The Vehicle Routing Problem, Society for Industrial and Applied Mathematic (SIAM), 0-89871-498-2
  27. 27. ThangiahS. R. 1998 Genetic Algorithms, Tabu Search and Simulated Annealing Methods for Vehicle Routing Problems with Time Windows, In: Practical Handbook of Genetic Algorithms: Complex Structures, Vol. III: Complex structures, L. D. Chambers (Eds.), 347381 , CRC Press, 0-84932-539-0
  28. 28. WagnerS.AffenzellerM. 2004 The HeuristicLab Optimization Environment. Technical Report, Institute of Formal Models and Verification. Johannes Kepler University Linz. Austria
  29. 29. YamadaT.NakanoR. 1997 Genetic Algorithms for Job-Shop Scheduling Problems, Proceedings of Modern Heuristic for Decision Support, 6781 , London, 18-19 March 1997, UNICOM seminar

Written By

Jorge A. Ruiz-Vanoye, Ocotlan Diaz-Parra, Joaquin Perez-Ortega, Rodolfo A. Pazos R., Gerardo Reyes Salgado and Juan Javier Gonzalez-Barbosa

Published: 01 February 2010