Location Routing Problem (LRP)¶

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

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

    // Number of customers
    int nbCustomers;

    // Customers coordinates
    int[] xCustomers;
    int[] yCustomers;

    // Customers demands
    int[] demandsData;

    // Number of depots
    int nbDepots;

    // Depots coordinates
    int[] xDepots;
    int[] yDepots;

    // Capacity of depots
    int[] depotsCapacity;
    double[] openingDepotsCost;

    // Number of trucks
    int nbTrucks;

    // Capacity of a truck
    int truckCapacity;

    // Cost of opening a route
    int openingRouteCost;

    // Is the route used ?
    LSExpression[] sequenceUsed;

    // What is the depot of the route ?
    LSExpression[] associatedDepot;

    // Distance matrixes
    double[][] distMatrixData;
    double[][] distDepotsData;

    int areCostDouble;

    // Decision variables
    LSExpression[] customersSequences;
    LSExpression[] depots;

    // Sum of all the costs
    LSExpression totalCost;

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

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] line;
            line = ReadNextLine(input);
            nbCustomers = int.Parse(line[0]);
            xCustomers = new int[nbCustomers];
            yCustomers = new int[nbCustomers];
            demandsData = new int[nbCustomers];
            distMatrixData = new double[nbCustomers][];

            line = ReadNextLine(input);
            nbDepots = int.Parse(line[0]);
            xDepots = new int[nbDepots];
            yDepots = new int[nbDepots];
            depotsCapacity = new int[nbDepots];
            openingDepotsCost = new double[nbDepots];
            distDepotsData = new double[nbCustomers][];

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

            for (int i = 0; i < nbCustomers; ++i)
            {
                line = ReadNextLine(input);
                xCustomers[i] = int.Parse(line[0]);
                yCustomers[i] = int.Parse(line[1]);
            }
            line = ReadNextLine(input);
            line = ReadNextLine(input);
            truckCapacity = int.Parse(line[0]);
            line = ReadNextLine(input);

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

            double[] tempOpeningCostDepots = new double[nbDepots];
            for (int i = 0; i < nbDepots; ++i)
            {
                line = ReadNextLine(input);
                tempOpeningCostDepots[i] = double.Parse(
                    line[0],
                    System.Globalization.CultureInfo.InvariantCulture
                );
            }
            line = ReadNextLine(input);
            line = ReadNextLine(input);
            double tempOpeningCostRoute = double.Parse(line[0]);
            line = ReadNextLine(input);
            line = ReadNextLine(input);
            areCostDouble = int.Parse(line[0]);

            if (areCostDouble == 1)
            {
                openingRouteCost = (int)tempOpeningCostRoute;
                for (int i = 0; i < nbDepots; ++i)
                    openingDepotsCost[i] = tempOpeningCostDepots[i];
            }
            else
            {
                openingRouteCost = (int)Math.Round(tempOpeningCostRoute);
                for (int i = 0; i < nbDepots; ++i)
                    openingDepotsCost[i] = Math.Round(tempOpeningCostDepots[i]);
            }
            DistanceMatrixes();
        }
    }

    void DistanceMatrixes()
    {
        for (int i = 0; i < nbCustomers; ++i)
        {
            distMatrixData[i] = new double[nbCustomers];
            for (int j = 0; j < nbCustomers; ++j)
            {
                distMatrixData[i][j] = ComputeDistance(
                    xCustomers[i],
                    yCustomers[i],
                    xCustomers[j],
                    yCustomers[j]
                );
            }
            distDepotsData[i] = new double[nbDepots];
            for (int d = 0; d < nbDepots; ++d)
            {
                distDepotsData[i][d] = ComputeDistance(
                    xCustomers[i],
                    yCustomers[i],
                    xDepots[d],
                    yDepots[d]
                );
            }
        }
    }

    double ComputeDistance(int xi, int yi, int xj, int yj)
    {
        double dist = Math.Sqrt(Math.Pow(xi - xj, 2) + Math.Pow(yi - yj, 2));
        if (areCostDouble == 0)
            dist = Math.Ceiling(dist * 100);
        return dist;
    }

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

    void Solve(int limit)
    {
        // Declare the optimization model
        LSModel m = localsolver.GetModel();
        int totalDemand = 0;
        foreach (int dem in demandsData)
            totalDemand += dem;
        int minNbTrucks = (int)Math.Ceiling((double)totalDemand / truckCapacity);
        nbTrucks = (int)Math.Ceiling(1.5 * minNbTrucks);

        customersSequences = new LSExpression[nbTrucks];
        depots = new LSExpression[nbDepots];

        // A route is represented as a list containing the customers in the order they are visited
        for (int r = 0; r < nbTrucks; ++r)
            customersSequences[r] = m.List(nbCustomers);
        // All customers should be assigned to a route
        m.Constraint(m.Partition(customersSequences));
        // A depot is represented as a set containing the associated sequences
        for (int d = 0; d < nbDepots; ++d)
            depots[d] = m.Set(nbTrucks);
        // All the sequences should be assigned to a depot
        m.Constraint(m.Partition(depots));

        // Create LocalSolver arrays to be able to access them with "at" operators
        LSExpression demands = m.Array(demandsData);
        LSExpression distMatrix = m.Array(distMatrixData);
        LSExpression distDepots = m.Array(distDepotsData);
        sequenceUsed = new LSExpression[nbTrucks];
        LSExpression[] routeCosts = new LSExpression[nbTrucks];
        LSExpression[] distRoutes = new LSExpression[nbTrucks];
        associatedDepot = new LSExpression[nbTrucks];
        LSExpression quantityServed = m.Array();

        for (int r = 0; r < nbTrucks; ++r)
        {
            LSExpression sequence = customersSequences[r];
            LSExpression c = m.Count(sequence);

            // A sequence is used if it serves at least one customer
            sequenceUsed[r] = m.Gt(c, 0);
            // The "find" function gets the depot that is assigned to the sequence
            associatedDepot[r] = m.Find(m.Array(depots), r);

            LSExpression demandLambda = m.LambdaFunction(j => demands[j]);
            quantityServed.AddOperand(m.Sum(sequence, demandLambda));
            // The quantity needed in each sequence must not exceed the vehicle capacity
            m.Constraint(quantityServed[r] <= truckCapacity);

            LSExpression distLambda = m.LambdaFunction(
                i => m.At(distMatrix, m.At(sequence, i), m.At(sequence, i + 1))
            );

            distRoutes[r] =
                m.Sum(m.Range(0, c - 1), distLambda)
                + m.If(
                    sequenceUsed[r],
                    m.At(distDepots, m.At(sequence, 0), associatedDepot[r])
                        + m.At(distDepots, m.At(sequence, c - 1), associatedDepot[r]),
                    0
                );
            // The sequence cost is the sum of the opening cost and the sequence length
            routeCosts[r] = distRoutes[r] + openingRouteCost * sequenceUsed[r];
        }
        LSExpression[] depotCost = new LSExpression[nbDepots];
        for (int d = 0; d < nbDepots; ++d)
        {
            // A depot is open if at least a sequence starts from there
            depotCost[d] = openingDepotsCost[d] * (m.Count(depots[d]) > 0);
            LSExpression depotLambda = m.LambdaFunction(r => m.At(quantityServed, r));
            LSExpression depotQuantity = m.Sum(depots[d], depotLambda);
            // The total demand served by a depot must not exceed its capacity
            m.Constraint(depotQuantity <= depotsCapacity[d]);
        }
        LSExpression depotsCost = m.Sum(depotCost);
        LSExpression routingCost = m.Sum(routeCosts);
        totalCost = routingCost + depotsCost;

        m.Minimize(totalCost);
        m.Close();

        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 cost = " + totalCost.GetDoubleValue()
            );
            for (int r = 0; r < nbTrucks; ++r)
            {
                if (sequenceUsed[r].GetValue() != 0)
                {
                    output.Write(
                        "Route " + r + ", assigned to depot " + associatedDepot[r].GetValue() + ": "
                    );
                    LSCollection customersCollection = customersSequences[r].GetCollectionValue();
                    for (int i = 0; i < customersCollection.Count(); ++i)
                        output.Write(customersCollection[i] + " ");
                    output.WriteLine();
                }
            }
        }
    }

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

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

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