Vehicule routing problem¶

/********** Cvrp.cs **********/

using System;
using System.IO;
using localsolver;


public class Cvrp : IDisposable
{
    // Solver
    LocalSolver localsolver;

    // Number of customers
    int nbCustomers;

    // Capacity of the trucks
    int truckCapacity;

    // Demand on each node
    long[] demands;

    // Distance matrix
    long[][] distanceMatrix;

    // Number of trucks
    int nbTrucks;

    // Decision variables
    LSExpression[] customersSequences;
    
    // Are the trucks actually used
    LSExpression[] trucksUsed;

    // Number of trucks used in the solution
    LSExpression nbTrucksUsed;

    // Distance travelled by all the trucks
    LSExpression totalDistance;

    public Cvrp (string strNbTrucks)
    {
        localsolver = new LocalSolver();
        nbTrucks = int.Parse(strNbTrucks);
    }

    /* Reads instance data. */
    void ReadInstance(string fileName)
    {
        readInputCvrp(fileName);

        // The number of trucks is usually given in the name of the file
        // nbTrucks can also be given in command line
        if (nbTrucks == 0) nbTrucks = getNbTrucks(fileName);
    }

    public void Dispose ()
    {
        localsolver.Dispose();
    }

    void Solve(int limit)
    {
        /* Declares the optimization model. */
        LSModel model = localsolver.GetModel();

        // Sequence of customers visited by each truck.
        // When n >= count(customersSequences[k]) (after the last visited
        // customer), customersSequences[k][n] = -1
        customersSequences = new LSExpression[nbTrucks];
        for (int k = 0; k < nbTrucks; k++)
        {
            customersSequences[k] = model.List(nbCustomers);
        }

        // All customers must be visited by  the trucks
        model.Constraint(model.Partition(customersSequences));

        // Each truck starts (n=0) and ends (n=nbCustomers+1) at the depot (index 0)
        LSExpression[,] nodeOnVisits = new LSExpression[nbTrucks,nbCustomers+2];
        for (int k = 0; k < nbTrucks; k++)
        {
            nodeOnVisits[k,0] = model.CreateConstant(0);
            nodeOnVisits[k,nbCustomers+1] = model.CreateConstant(0);
        }

        // During the route, the actual node visited is 1 + customersSequences[k][n]:
        //  - When n < count(customersSequences[k]) (when a customer is on the nth 
        //      position), nodeOnVisits[k][n+1] = cutomerId. (actual customers ids are 
        //      in [1..nbCustomers], 0 being the warehouse)
        //  - When n >= count(customersSequences[k]) (when the last customer has already 
        //      been visited), nodeOnVisits[k][n+1] = 0 (the warehouse id)
        for (int k = 0; k < nbTrucks; k++)
        {
            for (int n = 1; n < nbCustomers + 1; n++)
            {
                nodeOnVisits[k,n] = 1 + customersSequences[k][n-1];
            }
        }

        // A truck is used if it visits at least one customer
        trucksUsed = new LSExpression[nbTrucks];
        for (int k = 0; k < nbTrucks; k++)
        {
            trucksUsed[k] = model.Count(customersSequences[k]) > 0;
        }
        nbTrucksUsed = model.Sum(trucksUsed);

        // Create demands as an array to be able to access it with an "at" operator
        LSExpression demandsArray = model.Array(demands);

        // The quantity needed in each route must not exceed the truck capacity
        for (int k = 0; k < nbTrucks; k++)
        {
            LSExpression routeQuantity = model.Sum();
            for (int n = 1; n < nbCustomers + 1; n++)
            {
                routeQuantity.AddOperand(demandsArray[nodeOnVisits[k,n]]);
            }
            model.Constraint(routeQuantity <= truckCapacity);
        }

        // Create distance as an array to be able to acces it with an "at" operator
        LSExpression distanceArray = model.Array();
        for (int n = 0; n < nbCustomers + 1; n++)
        {
            distanceArray.AddOperand(model.Array(distanceMatrix[n]));
        }

        // Distance traveled by each truck
        LSExpression[] routeDistances = new LSExpression[nbTrucks];
        for (int k = 0; k < nbTrucks; k++)
        {
            routeDistances[k] = model.Sum();
            for (int n = 0; n < nbCustomers + 1; n++)
            {
                // Distance traveled from node n to node n+1 by truck k
                // distanceArray[a, b] is a shortcut for accessing the multi-dimensional array
                // distanceArray with an at operator. Same as model.At(distanceArray, a, b)
                routeDistances[k].AddOperand(distanceArray[nodeOnVisits[k,n], nodeOnVisits[k,n+1]]);
            }
        }

        // Total distance travelled
        totalDistance = model.Sum(routeDistances);

        // Objective: minimize the number of trucks used, then minimize the distance travelled
        model.Minimize(nbTrucksUsed);
        model.Minimize(totalDistance);

        model.Close();
        
        /* Parameterizes the solver. */
        LSPhase phase = localsolver.CreatePhase();
        phase.SetTimeLimit(limit);

        localsolver.Solve();
    }

    /* Writes the solution in a file with the following format :
     *  - number of trucks used and total distance
     *  - for each truck the nodes visited (omitting the start/end at the depot)*/
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(nbTrucksUsed.GetValue() + " " + totalDistance.GetValue());
            for (int k = 0; k < nbTrucks; k++)
            {
                if (trucksUsed[k].GetValue() != 1) continue;
                // Values in sequence are in [0..nbCustomers-1]. +2 is to put it back in [2..nbCustomers+1]
                // as in the data files (1 being the depot)
                LSCollection customersCollection = customersSequences[k].GetCollectionValue();
                for (int i = 0; i < customersCollection.Count(); i++)
                {
                    output.Write((customersCollection[i] + 2) + " ");
                }
                output.WriteLine();
            }
        }
    }
    
    public static void Main (string[] args)
    {
        if (args.Length < 1) 
        {
            Console.WriteLine ("Usage: Cvrp inputFile [solFile] [timeLimit] [nbTrucks]");
            System.Environment.Exit (1);
        }
        String instanceFile = args [0];
        String outputFile = args.Length > 1 ? args [1] : null;
        String strTimeLimit = args.Length > 2 ? args [2] : "20";
        String strNbTrucks = args.Length > 3 ? args [3] : "0";

        using (Cvrp model = new Cvrp(strNbTrucks)) 
        {
            model.ReadInstance (instanceFile);
            model.Solve (int.Parse (strTimeLimit));
            if (outputFile != null)
                model.WriteSolution (outputFile);
        }
    }

    /* The input files follow the "Augerat" format.*/
    private void readInputCvrp(string fileName) 
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            int nbNodes = 0;
            string[] splitted;
            while (true) 
            {
                splitted = input.ReadLine().Split(':');
                if(splitted[0].Contains("DIMENSION"))
                {
                    nbNodes = int.Parse(splitted[1]);
                    nbCustomers = nbNodes - 1;
                }
                else if (splitted[0].Contains("CAPACITY"))
                {
                    truckCapacity = int.Parse(splitted[1]);
                }
                else if (splitted[0].Contains("EDGE_WEIGHT_TYPE"))
                {
                    if (!splitted[1].Trim().Equals("EUC_2D"))
                    {
                        Console.WriteLine("Edge Weight Type " + splitted[1] + " is not supported (only EUC_2D)");
                        System.Environment.Exit(1);
                    }
                }
                else if (splitted[0].Contains("NODE_COORD_SECTION"))
                {
                    break;
                }
            }
            int[] nodesX = new int[nbNodes];
            int[] nodesY = new int[nbNodes];
            for (int n = 0; n < nbNodes; n++)
            {
                splitted = input.ReadLine().Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
                if (int.Parse(splitted[0]) != n+1)
                {
                    Console.WriteLine("Unexpected index");
                    System.Environment.Exit(1);
                }
                nodesX[n] = int.Parse(splitted[1]);
                nodesY[n] = int.Parse(splitted[2]);
            }

            computeDistanceMatrix(nodesX, nodesY);

            splitted = input.ReadLine().Split(':');
            if (!splitted[0].Contains("DEMAND_SECTION"))
            {
                Console.WriteLine("Expected keyword DEMAND_SECTION");
                System.Environment.Exit(1);
            }

            demands = new long[nbNodes];
            for (int n = 0; n < nbNodes; n++)
            {
                splitted = input.ReadLine().Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
                if (int.Parse(splitted[0]) != n+1)
                {
                    Console.WriteLine("Unexpected index");
                    System.Environment.Exit(1);
                }
                demands[n] = int.Parse(splitted[1]);
            }

            splitted = input.ReadLine().Split(':');
            if (!splitted[0].Contains("DEPOT_SECTION"))
            {
                Console.WriteLine("Expected keyword DEPOT_SECTION");
                System.Environment.Exit(1);
            }

            int warehouseId = int.Parse(input.ReadLine());
            if (warehouseId != 1)
            {
                Console.WriteLine("Warehouse id is supposed to be 1");
                System.Environment.Exit(1);
            }

            int endOfDepotSection = int.Parse(input.ReadLine());
            if (endOfDepotSection != -1)
            {
                Console.WriteLine("Expecting only one warehouse, more than one found");
                System.Environment.Exit(1);
            }

            if (demands[0] != 0)
            {
                Console.WriteLine("Warehouse demand is supposed to be 0");
                System.Environment.Exit(1);
            }
        }
    }

    /* Computes the distance matrix */
    private void computeDistanceMatrix(int[] nodesX, int[] nodesY)
    {
        distanceMatrix = new long[nbCustomers+1][];
        for (int i = 0; i < nbCustomers + 1; i++)
        {
            distanceMatrix[i] = new long[nbCustomers+1];
        }
        for (int i = 0; i < nbCustomers + 1; i++)
        {
            distanceMatrix[i][i] = 0;
            for (int j = i + 1; j < nbCustomers + 1; j++)
            {
                long dist = computeDist(nodesX[i], nodesX[j], nodesY[i], nodesY[j]);
                distanceMatrix[i][j] = dist;
                distanceMatrix[j][i] = dist;
            }
        }
    }

    private long computeDist(int xi, int xj, int yi, int yj)
    {
        double exactDist = Math.Sqrt(Math.Pow(xi - xj, 2) + Math.Pow(yi - yj, 2));
        return Convert.ToInt64(Math.Round(exactDist));
    }

    private int getNbTrucks(string fileName)
    {
        string[] splitted = fileName.Split(new Char[] {'-', 'k'}, StringSplitOptions.RemoveEmptyEntries);
        if (splitted.Length >= 2)
        {
            String toSplit = splitted[splitted.Length - 1];
            splitted = toSplit.Split(new Char[] {'.'}, StringSplitOptions.RemoveEmptyEntries);
            return int.Parse(splitted[0]);
        }
        Console.WriteLine("Error: nbTrucks could not be read from the file name. Enter it from the command line");
        System.Environment.Exit(1);
        return -1;
    }
}