Multi Depot Vehicle Routing Problem (MDVRP)¶

using localsolver;
using System;
using System.IO;
using System.Collections.Generic;

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

    // Number of customers
    int nbCustomers;

    // Number of depots/warehouses
    int nbDepots;

    //Number of trucks per depot
    int nbTrucksPerDepot;

    // Capacity of the trucks per depot
    long[] truckCapacity;

    // Duration capacity of the trucks per depot
    long[] routeDurationCapacity;

    // Service time per customer
    long[] serviceTimeData;

    // Demand per customer
    long[] demandsData;

    // Distance matrix between customers
    double[][] distanceMatrixCustomersData;

    // Distances between customers and depots
    double[][] distanceWarehouseData;

    // Decision variable
    LSExpression[][] customersSequences;

    // Distance traveled by all the trucks
    LSExpression totalDistance;

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

    void ReadInstance(string fileName)
    {
        readInputMdvrp(fileName);
    }

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

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

        // Sequence of customers visited by each truck
        customersSequences = new LSExpression[nbDepots][];

        // Vectorization for partition constraint
        LSExpression[] customersSequencesConstraint = new LSExpression[nbTrucksPerDepot * nbDepots];

        for (int d = 0; d < nbDepots; ++d)
        {
            customersSequences[d] = new LSExpression[nbTrucksPerDepot];
            for (int k = 0; k < nbTrucksPerDepot; ++k)
            {
                customersSequences[d][k] = model.List(nbCustomers);
                customersSequencesConstraint[d * nbTrucksPerDepot + k] = customersSequences[d][k];
            }
        }

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

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

        LSExpression distMatrix = model.Array(distanceMatrixCustomersData);

        //Distances for each truck from each depot 
        LSExpression[][] routeDistances = new LSExpression[nbDepots][];

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

        for (int d = 0; d < nbDepots; ++d)
        {
            routeDistances[d] = new LSExpression[nbTrucksPerDepot];
            LSExpression distDepot = model.Array(distanceWarehouseData[d]);
            for (int k = 0; k < nbTrucksPerDepot; ++k)
            {
                LSExpression sequence = customersSequences[d][k];
                LSExpression c = model.Count(sequence);

                // The quantity needed in each route must not exceed the truck capacity
                LSExpression demandLambda = model.LambdaFunction(j => demands[j]);
                LSExpression routeQuantity = model.Sum(sequence, demandLambda);
                model.Constraint(routeQuantity <= truckCapacity[d]);

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

                totalDistance.AddOperand(routeDistances[d][k]);

                // We add service time
                LSExpression serviceLambda = model.LambdaFunction(j => serviceTime[j]);
                LSExpression routeServiceTime = model.Sum(sequence, serviceLambda);

                // The total distance should not exceed the duration capacity of the truck
                // (only if we define such a capacity)
                if (routeDurationCapacity[d] > 0)
                {
                    model.Constraint(routeDistances[d][k] + routeServiceTime <= routeDurationCapacity[d]);
                }
            }
        }

        // 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 with the following format:
    //  - instance, time_limit, total distance
    //  - for each depot and for each truck in this depot, the customers visited 
    void WriteSolution(string fileName, string instanceFile, string timeLimit)
    {
        using (StreamWriter outfile = new StreamWriter(fileName))
        {
            outfile.WriteLine("Instance: " + instanceFile + " ; time_limit: " + timeLimit +
                    " ; Objective value: " + totalDistance.GetDoubleValue());
            for (int d = 0; d < nbDepots; ++d)
            {
                List<int> trucksUsed = new List<int>();
                for (int k = 0; k < nbTrucksPerDepot; ++k)
                {
                    if (customersSequences[d][k].GetCollectionValue().Count() > 0)
                    {
                        trucksUsed.Add(k);
                    }
                }

                if (trucksUsed.Count > 0)
                {
                    outfile.WriteLine("Depot " + (d + 1));
                    for (int k = 0; k < trucksUsed.Count; ++k)
                    {
                        outfile.Write("Truck " + (k + 1) + " : ");
                        LSCollection customersCollection = customersSequences[d][trucksUsed[k]].GetCollectionValue();
                        for (int p = 0; p < customersCollection.Count(); ++p)
                            outfile.Write((customersCollection[p] + 1) + " ");
                        outfile.WriteLine();
                    }
                    outfile.WriteLine();
                }
            }
        }
    }

    // Input files following "Cordeau"'s format
    private void readInputMdvrp(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] splitted;
            splitted = input
                    .ReadLine()
                    .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);

            // Numbers of trucks per depot, customers and depots
            nbTrucksPerDepot = int.Parse(splitted[1]);
            nbCustomers = int.Parse(splitted[2]);
            nbDepots = int.Parse(splitted[3]);

            routeDurationCapacity = new long[nbDepots];
            truckCapacity = new long[nbDepots];

            for (int d = 0; d < nbDepots; ++d)
            {
                splitted = input
                    .ReadLine()
                    .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);

                routeDurationCapacity[d] = int.Parse(splitted[0]);
                truckCapacity[d] = int.Parse(splitted[1]);
            }

            // Coordinates X and Y, service time and demand for customers
            double[] nodesX = new double[nbCustomers];
            double[] nodesY = new double[nbCustomers];
            serviceTimeData = new long[nbCustomers];
            demandsData = new long[nbCustomers];

            for (int n = 0; n < nbCustomers; ++n)
            {
                splitted = input
                    .ReadLine()
                    .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);

                nodesX[n] = double.Parse(splitted[1]);
                nodesY[n] = double.Parse(splitted[2]);
                serviceTimeData[n] = int.Parse(splitted[3]);
                demandsData[n] = int.Parse(splitted[4]);
            }

            // Coordinates X and Y for depots
            double[] DepotX = new double[nbDepots];
            double[] DepotY = new double[nbDepots];

            for (int d = 0; d < nbDepots; ++d)
            {
                splitted = input
                    .ReadLine()
                    .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);

                DepotX[d] = double.Parse(splitted[1]);
                DepotY[d] = double.Parse(splitted[2]);
            }

            // Compute the distance matrices
            ComputeDistanceMatrixCustomers(nodesX, nodesY);
            ComputeDistanceWarehouse(DepotX, DepotY, nodesX, nodesY);
        }
    }

    // Compute the distance matrix for customers
    private void ComputeDistanceMatrixCustomers(double[] nodesX, double[] nodesY)
    {
        distanceMatrixCustomersData = new double[nbCustomers][];

        for (int i = 0; i < nbCustomers; ++i)
            distanceMatrixCustomersData[i] = new double[nbCustomers];

        for (int i = 0; i < nbCustomers; ++i)
        {
            distanceMatrixCustomersData[i][i] = 0;
            for (int j = i + 1; j < nbCustomers; ++j)
            {
                double dist = ComputeDist(nodesX[i], nodesX[j], nodesY[i], nodesY[j]);
                distanceMatrixCustomersData[i][j] = dist;
                distanceMatrixCustomersData[j][i] = dist;
            }
        }

    }

    // Compute the distance matrix for depots/warehouses
    private void ComputeDistanceWarehouse(double[] DepotX, double[] DepotY, double[] nodesX, double[] nodesY)
    {
        distanceWarehouseData = new double[nbDepots][];

        for (int d = 0; d < nbDepots; ++d)
        {
            distanceWarehouseData[d] = new double[nbCustomers];
            for (int i = 0; i < nbCustomers; ++i)
            {
                distanceWarehouseData[d][i] = ComputeDist(nodesX[i], DepotX[d], nodesY[i], DepotY[d]);
            }
        }
    }

    private double ComputeDist(double xi, double xj, double yi, double yj)
    {
        return Math.Sqrt(Math.Pow(xi - xj, 2) + Math.Pow(yi - yj, 2));
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Mdvrp inputFile [outputFile] [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 (Mdvrp model = new Mdvrp())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile, instanceFile, strTimeLimit);
        }
    }

}