Prize-Collecting Vehicle Routing (PCVRP)¶

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

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

    // Number of customers
    int nbCustomers;

    // Capacity of the trucks
    int truckCapacity;

    // Minimum number of demands to satisfy
    long demandsToSatisfy;

    // Demand on each customer
    long[] demandsData;

    // Prize on each customer
    long[] prizesData;

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

    // Distances between customers and depot
    long[] distDepotData;

    // 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 traveled by all the trucks
    LSExpression totalDistance;

    // Total prize of the solution
    LSExpression totalPrize;

    // Total nb demands satisfied in the solution
    LSExpression totalQuantity;

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

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        ReadInputPcvrp(fileName);
    }

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

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

        trucksUsed = new LSExpression[nbTrucks];
        customersSequences = new LSExpression[nbTrucks];
        LSExpression[] distRoutes = new LSExpression[nbTrucks];
        LSExpression[] routeQuantities = new LSExpression[nbTrucks];
        LSExpression[] routePrizes = new LSExpression[nbTrucks];

        // Sequence of customers visited by each truck
        for (int k = 0; k < nbTrucks; ++k)
            customersSequences[k] = model.List(nbCustomers);

        // A customer might be visited by only one truck
        model.Constraint(model.Disjoint(customersSequences));

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

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

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

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

            // 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, distDepot[sequence[0]] + distDepot[sequence[c - 1]], 0);
            
            // Route prize of truck k
            LSExpression prizeLambda = model.LambdaFunction(j => prizes[j]);
            routePrizes[k] = model.Sum(sequence, prizeLambda);
        }
        
        // Minimal number of demands to satisfy
        totalQuantity = model.Sum(routeQuantities);
        model.Constraint(totalQuantity >= demandsToSatisfy);

        totalPrize = model.Sum(routePrizes);
        nbTrucksUsed = model.Sum(trucksUsed);
        totalDistance = model.Sum(distRoutes);

        // Objective: minimize the number of trucks used, then maximize the total prize and minimize the distance traveled
        model.Minimize(nbTrucksUsed);
        model.Maximize(totalPrize);
        model.Minimize(totalDistance);

        model.Close();

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

        localsolver.Solve();
    }

   /* Write the solution in a file with the following format:
    * - total prize, number of trucks used and total distance
    * - for each truck the customers visited (omitting the start/end at the depot)
    * - number of unvisited customers, demands satisfied */
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(totalPrize.GetValue() + " " + nbTrucksUsed.GetValue() + " " + totalDistance.GetValue());
            int nbUnvisitedCustomers = nbCustomers;
            for (int k = 0; k < nbTrucks; ++k)
            {
                if (trucksUsed[k].GetValue() != 1)
                    continue;
                // Values in sequence are in 0...nbCustomers. +1 is to put it back in 1...nbCustomers+1
                // as in the data files (0 being the depot)
                LSCollection customersCollection = customersSequences[k].GetCollectionValue();
                for (int i = 0; i < customersCollection.Count(); ++i)
                    output.Write((customersCollection[i] + 1) + " ");
                    --nbUnvisitedCustomers;
                output.WriteLine();
            }
            output.WriteLine(nbUnvisitedCustomers + " " + totalQuantity.GetValue());
        }
    }

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

    // The input files follow the "longjianyu" format
    private void ReadInputPcvrp(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] splitted;
            splitted = input
                    .ReadLine()
                    .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
            
            nbTrucks = int.Parse(splitted[0]);
            truckCapacity = int.Parse(splitted[1]);
            demandsToSatisfy = int.Parse(splitted[2]);

            int n = 0;
            List<int> customersXList = new List<int>(), customersYList = new List<int>();
            List<long> demandsDataList = new List<long>(), prizesDataList = new List<long>();
            int depotX = 0, depotY = 0;
            string line;

            while ((line = input.ReadLine()) != null)
            {
                splitted = line.Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
                if (int.Parse(splitted[0]) != n)
                    throw new Exception("Unexpected index");
                if (n == 0)
                {
                    depotX = int.Parse(splitted[1]);
                    depotY = int.Parse(splitted[2]);
                }
                else
                {
                    customersXList.Add(int.Parse(splitted[1]));
                    customersYList.Add(int.Parse(splitted[2]));
                    demandsDataList.Add(long.Parse(splitted[3]));
                    prizesDataList.Add(long.Parse(splitted[4]));
                }
                ++n;
            }

            nbCustomers = n - 1; 

            int[] customersX = customersXList.ToArray();
            int[] customersY = customersYList.ToArray();
            
            demandsData = demandsDataList.ToArray();
            prizesData = prizesDataList.ToArray();

            ComputeDistanceMatrix(depotX, depotY, customersX, customersY);
        }
    }

    // Compute the distance matrix
    private void ComputeDistanceMatrix(int depotX, int depotY, int[] customersX, int[] customersY)
    {
        distMatrixData = new long[nbCustomers][];
        for (int i = 0; i < nbCustomers; ++i)
            distMatrixData[i] = new long[nbCustomers];

        for (int i = 0; i < nbCustomers; ++i)
        {
            distMatrixData[i][i] = 0;
            for (int j = i + 1; j < nbCustomers; ++j)
            {
                long dist = ComputeDist(customersX[i], customersX[j], customersY[i], customersY[j]);
                distMatrixData[i][j] = dist;
                distMatrixData[j][i] = dist;
            }
        }

        distDepotData = new long[nbCustomers];
        for (int i = 0; i < nbCustomers; ++i)
            distDepotData[i] = ComputeDist(depotX, customersX[i], depotY, customersY[i]);
    }

    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));
    }
}