Car Sequencing¶

/********** CarSequencing.cs **********/

using System;
using System.IO;
using localsolver;

public class CarSequencing : IDisposable
{
    // Number of vehicles
    int nbPositions;

    // Number of options. 
    int nbOptions;

    // Number of classes. 
    int nbClasses;

    // Options properties. 
    int[] maxCarsPerWindow;
    int[] windowSize;

    // Classes properties. 
    int[] nbCars;
    int[][] options;

    // Initial sequence.
    int[] initialSequence;

    // Solver. 
    LocalSolver localsolver;

    // LS Program variable. 
    LSExpression sequence;

    // Objective.
    LSExpression totalViolations;

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

    // Reads instance data.
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] splitted = input.ReadLine().Split(' ');
            nbPositions = int.Parse(splitted[0]);
            nbOptions = int.Parse(splitted[1]);
            nbClasses = int.Parse(splitted[2]);

            splitted = input.ReadLine().Split(' ');

            maxCarsPerWindow = new int[nbOptions];

            for (int o = 0; o < nbOptions; o++)
                maxCarsPerWindow[o] = int.Parse(splitted[o]);

            splitted = input.ReadLine().Split(' ');

            windowSize = new int[nbOptions];

            for (int o = 0; o < nbOptions; o++)
                windowSize[o] = int.Parse(splitted[o]);

            options = new int[nbClasses][];
            nbCars = new int[nbClasses];
            initialSequence = new int[nbPositions];

            int pos = 0;
            for (int c = 0; c < nbClasses; c++)
            {
                splitted = input.ReadLine().Split(' ');
                nbCars[c] = int.Parse(splitted[1]);
                options[c] = new int[nbOptions];
                for (int o = 0; o < nbOptions; o++)
                {
                    int v = int.Parse(splitted[o + 2]);
                    options[c][o] = (v == 1) ? 1 : 0;
                }
                for (int p = pos; p < pos + nbCars[c]; p++)
                    initialSequence[p] = c;
                pos += nbCars[c];
            }
        }
    }

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

    void Solve(int limit)
    {
        localsolver = new LocalSolver();

        // Declares the optimization model.
        LSModel model = localsolver.GetModel();

        // sequence[i] = j if class initially planned on position j is produced on position i
        sequence = model.List(nbPositions);

        // sequence is a permutation of the initial production plan, all indexes must appear exactly once
        model.Constraint(model.Partition(sequence));

        // Create LocalSolver arrays to be able to access them with "at" operators
        LSExpression initialArray = model.Array(initialSequence);
        LSExpression optionArray = model.Array(options);

        // Number of cars with option o in each window
        LSExpression[][] nbCarsWindows = new LSExpression[nbOptions][];
        for (int o = 0; o < nbOptions; o++)
        {
            nbCarsWindows[o] = new LSExpression[nbPositions - windowSize[o] + 1];
            for (int j = 0; j < nbPositions - windowSize[o] + 1; j++)
            {
                nbCarsWindows[o][j] = model.Sum();
                for (int k = 0; k < windowSize[o]; k++)
                {
                    LSExpression classAtPosition = initialArray[sequence[j + k]];
                    nbCarsWindows[o][j].AddOperand(optionArray[classAtPosition, o]);
                }
            }
        }

        // Number of violations of option o capacity in each window
        LSExpression[][] nbViolationsWindows = new LSExpression[nbOptions][];
        for (int o = 0; o < nbOptions; o++)
        {
            nbViolationsWindows[o] = new LSExpression[nbPositions - windowSize[o] + 1];
            for (int j = 0; j < nbPositions - windowSize[o] + 1; j++)
            {
                nbViolationsWindows[o][j] = model.Max(0, nbCarsWindows[o][j] - maxCarsPerWindow[o]);
            }
        }

        // Minimize the sum of violations for all options and all windows
        totalViolations = model.Sum();
        for (int o = 0; o < nbOptions; o++)
        {
            totalViolations.AddOperands(nbViolationsWindows[o]);
        }

        model.Minimize(totalViolations);
        model.Close();

        // Set the initial solution
        sequence.GetCollectionValue().Clear();
        for (int p = 0; p < nbPositions; p++)
            sequence.GetCollectionValue().Add(p);

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

        localsolver.Solve();
    }

    // Writes the solution in a file following the following format: 
    // - 1st line: value of the objective;
    // - 2nd line: for each position p, index of class at positions p.
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(totalViolations.GetValue());
            for (int p = 0; p < nbPositions; p++)
            {
                output.Write(initialSequence[sequence.GetCollectionValue().Get(p)] + " ");
            }
            output.WriteLine();
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: CarSequencing 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] : "60";

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