Multi Trip Capacitated Vehicle Routing Problem (MTCVRP)¶

using System;
using System.IO;
using localsolver;

public class MultiTripVrp : IDisposable
{
    // LocalSolver
    LocalSolver localsolver;

    // Number of customers
    int nbCustomers;

    // Number of depots
    int nbDepots;

    // Number of depot copies
    int nbDepotCopies;

    // Total number of locations (customers, depots, depots copies)
    int nbTotalLocations;

    // Capacity of the trucks
    int truckCapacity;

    // Demand on each customer
    int[] demandsData;

    // Distance matrix between customers
    int[][] distMatrixData;

    // Number of trucks
    int nbTrucks;

    // Maximum distance traveled by a truck
    int maxDist;

    // Decision variables
    LSExpression[] visitOrders;

    // Are the trucks actually used
    LSExpression[] trucksUsed;

    // Distance traveled by all the trucks
    LSExpression totalDistance;

    public MultiTripVrp()
    {
        localsolver = new LocalSolver();
    }

    public void Dispose()
    {
        if (localsolver != null)
            localsolver.Dispose();
    }

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            nbDepotCopies = 20;
            maxDist = 400;
            string[] line;
            line = ReadNextLine(input);
            nbCustomers = int.Parse(line[0]);
            int[] customersX = new int[nbCustomers];
            int[] customersY = new int[nbCustomers];
            demandsData = new int[nbCustomers];

            line = ReadNextLine(input);
            nbDepots = int.Parse(line[0]);
            int[] depotsX = new int[nbDepots];
            int[] depotsY = new int[nbDepots];

            line = ReadNextLine(input);
            for (int i = 0; i < nbDepots; ++i)
            {
                line = ReadNextLine(input);
                depotsX[i] = int.Parse(line[0]);
                depotsY[i] = int.Parse(line[1]);
            }
            line = ReadNextLine(input);

            for (int i = 0; i < nbCustomers; ++i)
            {
                line = ReadNextLine(input);
                customersX[i] = int.Parse(line[0]);
                customersY[i] = int.Parse(line[1]);
            }
            line = ReadNextLine(input);
            line = ReadNextLine(input);
            truckCapacity = int.Parse(line[0]) / 2;
            line = ReadNextLine(input);

            // Ignore depot infos
            for (int i = 0; i < nbDepots; ++i)
            {
                ReadNextLine(input);
            }
            line = ReadNextLine(input);
            for (int i = 0; i < nbCustomers; ++i)
            {
                line = ReadNextLine(input);
                demandsData[i] = int.Parse(line[0]);
            }
            line = ReadNextLine(input);

            nbTotalLocations = nbCustomers + nbDepots * nbDepotCopies;

            nbTrucks = 3;

            ComputeDistanceMatrix(depotsX, depotsY, customersX, customersY);
        }
    }

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

        trucksUsed = new LSExpression[nbTrucks];
        visitOrders = new LSExpression[nbTrucks + 1];
        LSExpression[] distRoutes = new LSExpression[nbTrucks];

        // Locations visited by each truck (Customers and Depots)
        // Add copies of the depots (so that they can be visited multiple times)
        // Add an extra fictive truck (who will visit every depot that will not be visited by real trucks)
        for (int k = 0; k < nbTrucks + 1; ++k)
            visitOrders[k] = model.List(nbTotalLocations);

        // The fictive truck cannot visit customers
        for (int i = 0; i < nbCustomers; i++)
            model.Constraint(!(model.Contains(visitOrders[nbTrucks], i)));

        // All customers must be visited by exactly one truck
        model.Constraint(model.Partition(visitOrders));

        // Create LocalSolver arrays to be able to access them with an "at" operator
        LSExpression demands = model.Array(demandsData);
        LSExpression distMatrix = model.Array(distMatrixData);

        for (int k = 0; k < nbTrucks; ++k)
        {
            LSExpression sequence = visitOrders[k];
            LSExpression c = model.Count(sequence);

            // A truck is used if it visits at least one customer
            trucksUsed[k] = c > 0;

            // Compute the quantity in the truck at each step
            LSExpression routeQuantityLambda = model.LambdaFunction((i, prev) =>
                model.If(sequence[i] < nbCustomers, prev + demands[sequence[i]], 0));
            LSExpression routeQuantity = model.Array(model.Range(0, c), routeQuantityLambda, 0);
            // Trucks cannot carry more than their capacity
            LSExpression quantityLambda = model.LambdaFunction(i => routeQuantity[i] <= truckCapacity);
            model.Constraint(model.And(model.Range(0, c), quantityLambda));

            // Distance traveled by truck k
            LSExpression distLambda = model.LambdaFunction(i => distMatrix[sequence[i - 1], sequence[i]]);
            distRoutes[k] = model.Sum(model.Range(1, c), distLambda) +
                            model.If(c > 0, distMatrix[nbCustomers, sequence[0]] + distMatrix[sequence[c - 1], nbCustomers], 0);

            model.Constraint(distRoutes[k] <= maxDist);
        }

        // Total distance traveled
        totalDistance = model.Sum(distRoutes);

        // Objective: minimize the distance traveled
        model.Minimize(totalDistance);

        model.Close();

        // Parametrize the solver
        localsolver.GetParam().SetTimeLimit(limit);

        localsolver.Solve();
    }

    /* Write the solution in a file */
    void WriteSolution(string infile, string outfile)
    {
        using (StreamWriter output = new StreamWriter(outfile))
        {
            output.WriteLine(
                "File name: " + infile + "; total distance = " + totalDistance.GetValue()
            );
            for (int r = 0; r < nbTrucks; ++r)
            {
                if (trucksUsed[r].GetValue() == 1)
                {
                    output.Write(
                        "Truck " + r + ": "
                    );
                    LSCollection visitCollection = visitOrders[r].GetCollectionValue();
                    for (int i = 0; i < visitCollection.Count(); ++i)
                        output.Write(
                            (visitCollection[i] < nbCustomers ? visitCollection[i] : -(Math.Floor(Convert.ToDouble((visitCollection[i] - nbCustomers) / nbDepotCopies) + 1)))
                            + " ");
                    output.WriteLine();
                }
            }
        }
    }

    String[] ReadNextLine(StreamReader input)
    {
        return input.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    }


    private int 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.ToInt32(Math.Round(exactDist));
    }

    // Compute the distance matrix
    private void ComputeDistanceMatrix(int[] depotsX, int[] depotsY, int[] customersX, int[] customersY)
    {
        distMatrixData = new int[nbTotalLocations][];
        for (int i = 0; i < nbCustomers + nbDepots * nbDepotCopies; ++i)
            distMatrixData[i] = new int[nbTotalLocations];
        for (int i = 0; i < nbCustomers; ++i)
        {
            distMatrixData[i][i] = 0;
            for (int j = i + 1; j < nbCustomers; ++j)
            {
                int distance = computeDist(customersX[i], customersX[j], customersY[i], customersY[j]);
                distMatrixData[i][j] = distance;
                distMatrixData[j][i] = distance;
            }

            for (int d = 0; d < nbDepots; d++)
            {
                int distance = computeDist(customersX[i], depotsX[d], customersY[i], depotsY[d]);
                for (int c = 0; c < nbDepotCopies; c++)
                {
                    int j = nbCustomers + d * nbDepotCopies + c;
                    distMatrixData[i][j] = distance;
                    distMatrixData[j][i] = distance;
                }
            }
        }

        for (int i = nbCustomers; i < nbTotalLocations; i++)
        {
            // Going from one depot to an other is never worth it
            for (int j = nbCustomers; j < nbTotalLocations; j++)
                distMatrixData[i][j] = 100000;
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Multi-TripVrp inputFile [solFile] [timeLimit]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "20";

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

};