#!/usr/bin/env python3 # Copyright 2010-2025 Google LLC # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. """Solve the car sequencing problem as an optimization problem. Problem Description: The Car Sequencing Problem with Optimization ----------------------------------------------------------------- See https://en.wikipedia.org/wiki/Car_sequencing_problem for more details. We are tasked with determining the optimal production sequence for a set of cars on an assembly line. This is a classic and challenging combinatorial optimization problem with the following characteristics: Fixed Production Demand: There is a specific, non-negotiable number of cars of different types (or 'classes') that must be produced. In our case, we have 6 distinct classes of cars, and we must produce exactly 5 of each, for a total of 30 'real' cars. Diverse Car Configurations: Each car class is defined by a unique combination of optional features. For example, 'Class 1' might require a sunroof (Option 1) and a special engine (Option 4), while 'Class 3' only requires air conditioning (Option 2). Specialized Assembly Stations: The assembly line is composed of a series of specialized stations. Each station is responsible for installing one specific option. For example, there is one station for sunroofs, one for special engines, and so on. Capacity-Limited Stations: The core challenge of the problem lies here. The stations cannot handle an unlimited, dense flow of cars requiring their specific option. Their capacity is defined by a 'sliding window' constraint. For example, the sunroof station might have a constraint of 'at most 1 car with a sunroof in any sequence of 3 consecutive cars'. This means sequences like [Sunroof, No, No, Sunroof] are valid, but [Sunroof, No, Sunroof, No] are not. The Need for Spacing (Optimization): The combination of high demand for certain options and tight capacity constraints may make it impossible to produce the 30 real cars consecutively. To create a valid sequence, we may need to insert 'dummy' or 'filler' cars into the production line. These dummy cars have no options and therefore do not consume capacity at any station. They serve purely as spacers to break up dense sequences of option-heavy cars. The Goal: The objective is to find a production sequence that fulfills the demand for all 30 real cars while using the minimum number of dummy cars. This is equivalent to finding the shortest possible total production schedule (real cars + dummy cars). Modeling and Solution Approach with CP-SAT ------------------------------------------ To solve this problem, we use the CP-SAT solver from Google's OR-Tools library. This is a constraint programming approach, which works by defining variables, constraints, and an objective function. 1. Decision Variables The fundamental decision the solver must make is: 'Which class of car should be placed in each production slot?' We define a large number of boolean variables: produces[c][s]. This variable is True if a car of class c is scheduled in slot s, and False otherwise. We create these for all car classes (including the dummy class) and for an extended number of slots (30 real + a buffer of 20 for dummies). We introduce a key integer variable: makespan. This variable represents the total length of the 'meaningful' part of our schedule. It's the slot number where the first dummy car appears, after which all subsequent cars are also dummies. 2. Constraints (The Rules of the Game) We translate the problem's rules into mathematical constraints that the solver must obey: One Car Per Slot: For every production slot s, exactly one car class can be assigned. We enforce this using an AddExactlyOne constraint over all produces[c][s] variables for that slot. Fulfill Real Car Demand: The total number of times each real car class c appears across all slots must equal its required demand (5 in our case). This is a simple Add(sum(...) == 5) constraint. Station Capacity (Sliding Window): This is the most critical constraint. For each option (e.g., 'sunroof') and its capacity rule (e.g., '1 in 3'), we create constraints for every possible sliding window. For every subsequence of 3 slots, we sum up the produces variables corresponding to car classes that require that option and constrain this sum to be less than or equal to 1. Makespan Definition: This is the clever part of the model. We link our makespan objective variable to the placement of dummy cars using logical equivalences for each slot s: (makespan <= s) is equivalent to (slot s contains a dummy car) This ensures that if the solver chooses a makespan of 32, for example, it is forced to place dummy cars in slots 32, 33, 34, and so on. Conversely, if the solver is forced to place a dummy car in slot 32 to satisfy a capacity constraint, the makespan must be at most 32. 3. The Objective Function The objective is simple and directly tied to our goal: Minimize makespan: By instructing the solver to find a solution with the smallest possible value for the makespan variable, we are asking it to find the shortest possible production schedule that satisfies all the rules. This inherently minimizes the number of dummy cars used. By defining the problem in this way, we let the CP-SAT solver explore the vast search space of possible sequences efficiently, using its powerful constraint propagation and search techniques to find an optimal arrangement that meets all our complex requirements. """ from collections.abc import Sequence from absl import app from ortools.sat.python import cp_model def solve_car_sequencing_optimization() -> None: """Solves the car sequencing problem with an optimization approach.""" # -------------------- # 1. Data # -------------------- num_real_cars: int = 30 max_dummy_cars: int = 20 num_slots = num_real_cars + max_dummy_cars all_slots = range(num_slots) class_options = [ # Options: 1 2 3 4 5 [0, 0, 0, 0, 0], # Class 0 (Dummy) [1, 0, 0, 1, 0], # Class 1 [0, 1, 0, 0, 1], # Class 2 [0, 1, 0, 0, 0], # Class 3 [0, 0, 1, 1, 0], # Class 4 [0, 0, 1, 0, 0], # Class 5 [0, 0, 0, 0, 1], # Class 6 ] num_classes = len(class_options) all_classes = range(num_classes) real_classes = range(1, num_classes) dummy_class = 0 demands = [5, 5, 5, 5, 5, 5] capacity_constraints = [(1, 3), (1, 2), (1, 3), (2, 5), (1, 5)] num_options = len(capacity_constraints) all_options = range(num_options) classes_with_option = [ [c for c in real_classes if class_options[c][o] == 1] for o in all_options ] # -------------------- # 2. Model Creation # -------------------- model = cp_model.CpModel() # -------------------- # 3. Decision Variables # -------------------- produces = {} for c in all_classes: for s in all_slots: produces[(c, s)] = model.new_bool_var(f"produces_c{c}_s{s}") makespan = model.new_int_var(num_real_cars, num_slots, "makespan") # -------------------- # 4. Constraints # -------------------- # Constraint 1: Only one car produced per slot. for s in all_slots: model.add_exactly_one([produces[(c, s)] for c in all_classes]) # Constraint 2: Meet the demand of real cars. for i, c in enumerate(real_classes): model.add(sum(produces[(c, s)] for s in all_slots) == demands[i]) # Constraint 3: Enforce the capacity constraints on options. for o in all_options: max_cars, subsequence_len = capacity_constraints[o] for start in range(num_slots - subsequence_len + 1): window = range(start, start + subsequence_len) cars_with_option_in_window = [] for c in classes_with_option[o]: for s in window: cars_with_option_in_window.append(produces[(c, s)]) model.add(sum(cars_with_option_in_window) <= max_cars) # Constraint 4 (Link objective and dummy cars at the end of the schedule) for s in all_slots: makespan_le_s = model.new_bool_var(f"makespan_le_{s}") # Enforce makespan_le_s <=> (makespan <= s) model.add(makespan <= s).only_enforce_if(makespan_le_s) # Use ~ for negation model.add(makespan > s).only_enforce_if(~makespan_le_s) # Enforce makespan_le_s => produces[dummy_class, s] model.add_implication(makespan_le_s, produces[dummy_class, s]) # -------------------- # 5. Objective # -------------------- model.minimize(makespan) # -------------------- # 6. Solve and Print Solution # -------------------- solver = cp_model.CpSolver() solver.parameters.max_time_in_seconds = 30.0 solver.parameters.num_search_workers = 1 # The problem is easy to solve. # solver.parameters.log_search_progress = True # uncomment to see the log. status = solver.Solve(model) if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: final_makespan = int(solver.ObjectiveValue()) num_dummies_needed = final_makespan - num_real_cars print( f'\n{"Optimal" if status == cp_model.OPTIMAL else "Feasible"}' f" solution found with a makespan of {final_makespan}." ) print( f"This requires the conceptual equivalent of {num_dummies_needed} dummy" " car(s) to be used as spacers." ) sequence = [-1] * num_slots for s in all_slots: for c in all_classes: if solver.Value(produces[(c, s)]) == 1: sequence[s] = c break print("\nFull Production Sequence (Class 0 is dummy):") print("Slot: | " + " | ".join(f"{i:2}" for i in range(num_slots)) + " |") print("-------|-" + "--|-" * num_slots) print("Class: | " + " | ".join(f"{c:2}" for c in sequence) + " |") elif status == cp_model.INFEASIBLE: print("\nNo solution found.") else: print(f"\nSomething went wrong. Solver status: {status}") print("\nSolver statistics:") print(solver.response_stats()) def main(argv: Sequence[str]) -> None: if len(argv) > 1: raise app.UsageError("Too many command-line arguments.") solve_car_sequencing_optimization() if __name__ == "__main__": app.run(main)