Car Sequencing Color¶

/******** CarSequencingColor.java *********/

import java.util.*;
import java.io.*;
import localsolver.*;

public class CarSequencingColor {
    // Constantes for objective order
    private final int COLOR_HIGH_LOW = 0;
    private final int HIGH_LOW_COLOR = 1;
    private final int HIGH_COLOR_LOW = 2;
    private final int COLOR_HIGH = 3;
    private final int HIGH_COLOR = 4;

    // Number of vehicles.
    private int nbPositions;

    // Number of options.
    private int nbOptions;

    // Number of classes.
    private int nbClasses;

    // Paint batch limit.
    int paintBatchLimit;

    // Objective order.
    int objectiveOrder;

    // Start position.
    int startPosition;

    // Options properties.
    private int[] maxCarsPerWindow;
    private int[] windowSize;
    private boolean[] isPriorityOption;
    boolean hasLowPriorityOptions;

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

    // Initial sequence.
    private int[] initialSequence;

    // Solver.
    private final LocalSolver localsolver;

    // LS Program variables.
    private LSExpression sequence;

    // Objectives
    private LSExpression objectiveColor;
    private LSExpression objectiveHighPriority;
    private LSExpression objectiveLowPriority;

    private CarSequencingColor(LocalSolver localsolver) {
        this.localsolver = localsolver;
    }

    // Reads instance data.
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            nbPositions = input.nextInt();
            nbOptions = input.nextInt();
            nbClasses = input.nextInt();
            paintBatchLimit = input.nextInt();
            objectiveOrder = input.nextInt();
            startPosition = input.nextInt();

            maxCarsPerWindow = new int[nbOptions];
            windowSize = new int[nbOptions];
            isPriorityOption = new boolean[nbOptions];
            hasLowPriorityOptions = false;
            for (int o = 0; o < nbOptions; o++) {
                maxCarsPerWindow[o] = input.nextInt();
                windowSize[o] = input.nextInt();
                isPriorityOption[o] = input.nextInt() == 1;
                if (!isPriorityOption[o]) hasLowPriorityOptions = true;
            }

            if (!hasLowPriorityOptions) {
                if (objectiveOrder == COLOR_HIGH_LOW) objectiveOrder = COLOR_HIGH;
                else if (objectiveOrder == HIGH_COLOR_LOW) objectiveOrder = HIGH_COLOR;
                else if (objectiveOrder == HIGH_LOW_COLOR) objectiveOrder = HIGH_COLOR;
            }

            options = new int[nbClasses][nbOptions];
            nbCars = new int[nbClasses];
            colorClass = new int[nbClasses];
            for (int c = 0; c < nbClasses; c++) {
                colorClass[c] = input.nextInt();
                nbCars[c] = input.nextInt();
                for (int o = 0; o < nbOptions; o++) {
                    int v = input.nextInt();
                    options[c][o] = (v == 1) ? 1 : 0;
                }
            }

            initialSequence = new int[nbPositions];
            for (int p = 0; p < nbPositions; p++) {
                initialSequence[p] = input.nextInt();
            }
        }
    }

    private void solve(int limit) {
        // 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.listVar(nbPositions);

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

        // Past classes (before startPosition) can not move
        for (int p = 0; p < startPosition; p++)
            model.addConstraint(model.eq(model.at(sequence, p), p));

        // Create LocalSolver arrays to be able to access them with "at" operators
        LSExpression initialArray = model.array(initialSequence);
        LSExpression colorArray = model.array(colorClass);
        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++) {
            LSExpression oExpr = model.createConstant(o);
            nbCarsWindows[o] = new LSExpression[nbPositions];
            for (int j = startPosition - windowSize[o] + 1; j < nbPositions; j++) {
                nbCarsWindows[o][j] = model.sum();
                for (int k = 0; k < windowSize[o]; k++) {
                    if (j + k >= 0 && j + k < nbPositions) {
                        LSExpression classAtPosition = model.at(initialArray, model.at(sequence, j + k));
                        nbCarsWindows[o][j].addOperand(model.at(optionArray, classAtPosition, oExpr));
                    }
                }
            }
        }

        // Number of violations of option o capacity in each window
        objectiveHighPriority = model.sum();
        if (hasLowPriorityOptions) objectiveLowPriority = model.sum();
        for (int o = 0; o < nbOptions; o++) {
            LSExpression nbViolationsWindows = model.sum();
            for (int j = startPosition - windowSize[o] + 1; j < nbPositions; j++) {
                LSExpression delta = model.sub(nbCarsWindows[o][j], maxCarsPerWindow[o]);
                nbViolationsWindows.addOperand(model.max(0, delta));
            }
            if (isPriorityOption[o])
                objectiveHighPriority.addOperand(nbViolationsWindows);
            else
                objectiveLowPriority.addOperand(nbViolationsWindows);
        }

        // Color change between position p and position p+1
        LSExpression[] colorChange = new LSExpression[nbPositions - 1];
        objectiveColor = model.sum();
        for (int p = startPosition - 1; p < nbPositions - 1; p++) {
            LSExpression currentClass = model.at(initialArray, model.at(sequence, p));
            LSExpression nextClass = model.at(initialArray, model.at(sequence, p + 1));
            colorChange[p] = model.neq(model.at(colorArray, currentClass), model.at(colorArray, nextClass));
            objectiveColor.addOperand(colorChange[p]);
        }

        // Paint limit constraints : at least one change every paintBatchLimit positions
        for (int p = startPosition; p < nbPositions - paintBatchLimit - 1; p++) {
            LSExpression nodeOr = model.or();
            for (int p2 = 0; p2 < paintBatchLimit; p2++)
                nodeOr.addOperand(colorChange[p + p2]);
            model.addConstraint(nodeOr);
        }

        // Declare the objectives in the correct order
        switch (objectiveOrder) {
            case COLOR_HIGH_LOW:
                model.minimize(objectiveColor);
                model.minimize(objectiveHighPriority);
                model.minimize(objectiveLowPriority);
                break;
            case HIGH_COLOR_LOW:
                model.minimize(objectiveHighPriority);
                model.minimize(objectiveColor);
                model.minimize(objectiveLowPriority);
                break;
            case HIGH_LOW_COLOR:
                model.minimize(objectiveHighPriority);
                model.minimize(objectiveLowPriority);
                model.minimize(objectiveColor);
                break;
            case COLOR_HIGH:
                model.minimize(objectiveColor);
                model.minimize(objectiveHighPriority);
                break;
            case HIGH_COLOR:
                model.minimize(objectiveHighPriority);
                model.minimize(objectiveColor);
                break;
        }

        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 objectives;
    // - 2nd line: for each position p, index of class at positions p.
    private void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            output.print(objectiveColor.getValue() + " ");
            output.print(objectiveHighPriority.getValue() + " ");
            output.println(objectiveLowPriority.getValue());
            for (int p = 0; p < nbPositions; p++) {
                output.print(initialSequence[(int)sequence.getCollectionValue().get(p)] + " ");
            }
            output.println();
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java CarSequencingColor inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "60";

        try (LocalSolver localsolver = new LocalSolver()) {
            CarSequencingColor model = new CarSequencingColor(localsolver);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}