Car Sequencing¶

using System;
using System.IO;
using Hexaly.Optimizer;

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;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // LS Program variable
    HxExpression sequence;

    // Objective
    HxExpression totalViolations;

    public CarSequencing()
    {
        optimizer = new HexalyOptimizer();
    }

    /* Read 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 (optimizer != null)
            optimizer.Dispose();
    }

    void Solve(int limit)
    {
        optimizer = new HexalyOptimizer();

        // Declare the optimization model
        HxModel model = optimizer.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 HexalyOptimizer arrays to be able to access them with "at" operators
        HxExpression initialArray = model.Array(initialSequence);
        HxExpression optionArray = model.Array(options);

        // Number of cars with option o in each window
        HxExpression[][] nbCarsWindows = new HxExpression[nbOptions][];
        for (int o = 0; o < nbOptions; ++o)
        {
            nbCarsWindows[o] = new HxExpression[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)
                {
                    HxExpression classAtPosition = initialArray[sequence[j + k]];
                    nbCarsWindows[o][j].AddOperand(optionArray[classAtPosition, o]);
                }
            }
        }

        // Number of violations of option o capacity in each window
        HxExpression[][] nbViolationsWindows = new HxExpression[nbOptions][];
        for (int o = 0; o < nbOptions; ++o)
        {
            nbViolationsWindows[o] = new HxExpression[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);

        // Parametrize the optimizer
        optimizer.GetParam().SetTimeLimit(limit);

        optimizer.Solve();
    }

    /* Write the solution in a file with 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);
        }
    }
}