Solver for the Car Sequencing Problem on C++ using either Backtracking or an Evolutive Algorithm. Made for the Artificial Intelligence course (INF-295) at UTFSM, 2021-1.
Features a cross-over operator using Large Neighborhood Search (LNS) and a hybrid mutation operator.
To compile just run on your shell where the Makefile
is:
$ make install
Then, to use the solver:
$ ./bin/solver <path to instance file> <algorithm to use [evol/bt]> <n gens>
An already made file with the expected data and format can be found at instances/sample.txt
.
For cleaning objects and binary:
$ make clean
Based on Siala et al. (2015), in order to reliably/fastly get to a result for both the Evolutive Alg and the Backtracking Alg, variable instantiation was made following the most constrained vehicle class using the difficulty and utilities found on Gottlieb et al. (2003) on a "first-to-last" order.
Created randomly such that they already satisfy the demand constraints.
Uses the improved "sliding windows" function from Zhang et al.(2017), that can be expressed as "the number of required extra workers for an overloaded station". If this yields 0 then it means no (ratio) constraint was violated.