dypdl is a library for DyPDL modeling in Rust.
Modeling TSPTW using DyPDL.
```rust use dypdl::prelude::*;
// TSPTW instance. // 0 is the depot, and 1, 2, and 3 are customers. let ncustomers = 4; // Beginnings of time windows. let readytime = vec![0, 5, 0, 8]; // Ends of time windows. let duedate = vec![0, 16, 10, 14]; // Travel time. let distancematrix = vec![ vec![0, 3, 4, 5], vec![3, 0, 5, 4], vec![4, 5, 0, 3], vec![5, 4, 3, 0], ];
// Minimization and integer cost by default. let mut model = Model::default();
// Define an object type. let customer = model.addobjecttype("customer", n_customers).unwrap();
// Define state variables. // Unvisited customers, initially 1, 2, and 3. let unvisited = model.createset(customer, &[1, 2, 3]).unwrap(); let unvisited = model.addsetvariable("U", customer, unvisited).unwrap(); // Current location, initially 0. let location = model.addelementvariable("i", customer, 0).unwrap(); // Current time, less is better, initially 0. let time = model.addintegerresourcevariable("t", true, 0).unwrap();
// Define tables of constants.
let readytime: Table1DHandle
// Define transitions. let mut visits = vec![];
// Returning to the depot; let mut returntodepot = Transition::new("return to depot"); // The cost is the sum of the travel time and the cost of the next state. returntodepot.setcost(distance.element(location, 0) + IntegerExpression::Cost); // Update the current location to the depot. returntodepot.addeffect(location, 0).unwrap(); // Increase the current time. returntodepot.addeffect(time, time + distance.element(location, 0)).unwrap(); // Add the transition to the model. // When this transition is applicable, no need to consider other transitions. model.addforwardforcedtransition(returntodepot.clone()); visits.push(returntodepot);
for j in 1..ncustomers { // Visiting each customer. let mut visit = Transition::new(format!("visit {}", j)); visit.setcost(distance.element(location, j) + IntegerExpression::Cost); // Remove j from the set of unvisited customers. visit.addeffect(unvisited, unvisited.remove(j)).unwrap(); visit.addeffect(location, j).unwrap(); // Wait until the ready time. let arrivaltime = time + distance.element(location, j); let starttime = IntegerExpression::max(arrivaltime.clone(), readytime.element(j)); visit.addeffect(time, starttime).unwrap(); // The time window must be satisfied. visit.addprecondition( Condition::comparisoni(ComparisonOperator::Le, arrivaltime, duedate.element(j)) ); // Add the transition to the model. model.addforwardtransition(visit.clone()).unwrap(); visits.push(visit); }
// Define a base case. // If all customers are visited and the current location is the depot, the cost is 0. let isdepot = Condition::comparisone(ComparisonOperator::Eq, location, 0); model.addbasecase(vec![unvisited.isempty(), isdepot.clone()]).unwrap();
// Define redundant information, which is possibly useful for a solver. // Define state constraints. for j in 1..ncustomers { // The shortest arrival time, assuming the triangle inequality. let arrivaltime = time + distance.element(location, j); // The salesperson must be able to visit each unvisited customer before the deadline. let ontime = Condition::comparisoni( ComparisonOperator::Le, arrivaltime, duedate.element(j) ); model.addstateconstraint(!unvisited.contains(j) | on_time).unwrap(); }
// Define a dual bound.
// The minimum distance to each customer.
let mindistanceto = distancematrix.iter()
.enumerate()
.map(|(j, row)| row.iter().enumerate().filtermap(|(k, d)| {
if j == k {
None
} else {
Some(*d)
}
})
.min().unwrap()).collect();
let mindistanceto: Table1DHandle
// Solution. let solution = [visits[2].clone(), visits[3].clone(), visits[1].clone(), visits[0].clone()]; // Solution cost. let cost = 14; // Verify the solution. assert!(model.validate_forward(&solution, cost, true)); ```