1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

//! Strategies for generating an initial solution. More, different attampts can be found in commit
//! 725e48e0398db3fdee79db31adaf12d1ac0e4e35.

use rand;
use rand::Rng;
use rayon::prelude::*;
use std::i32;
use std::sync::Arc;

use model::{Action, OrderList, State, StateError, TravelTime, DUMP_LOCATION};

/// Randomly constructs an initial state. This works in a similar was as `create_greedy_state()`,
/// but orders with higher frequencies are also considered. This is done by selecting the optimal
/// day/vehicle combinations for every order.
pub fn create_greedy_stochastic_state(
    order_list: &Arc<OrderList>,
    travel_time: &Arc<TravelTime>,
) -> State {
    (0..8)
        .into_par_iter()
        .map(|_| {
            let mut rng = rand::weak_rng();
            let mut state = State::new(Arc::clone(order_list), Arc::clone(travel_time));

            for vehicle in 0..2 {
                for day in 0..5 {
                    let mut last_location = DUMP_LOCATION;

                    'plan_order: loop {
                        let mut sorted_orders: Vec<_> =
                            state.possible_orders.iter().cloned().collect();
                        sorted_orders.sort_unstable_by_key(|order_id| {
                            travel_time[&(last_location, order_list[order_id].location_id)]
                        });

                        for order_id in sorted_orders {
                            // We'll try a few vehicle/day combinations until one works. This is
                            // needed to support orders with frequenies above 1.
                            let possible_days: Vec<_> = order_list[&order_id]
                                .days()
                                .into_iter()
                                .filter(|&days| days.contains(&day))
                                .collect();
                            let chosen_days = (0..32)
                                .filter_map(|_| {
                                    let days: Vec<
                                        (usize, usize),
                                    > = rng.choose(&possible_days)?
                                        .into_iter()
                                        .map(|&order_day| {
                                            if order_day == day {
                                                (vehicle, order_day)
                                            } else {
                                                (rng.gen_range(0, 2), order_day)
                                            }
                                        })
                                        .collect();

                                    // We also want oto include combinations that go over capacity.
                                    // If we can't plan aything else, we'll simply insert more
                                    // segments later.
                                    let score = match state.try_insert_order_last(order_id, &days) {
                                        Ok((score, _)) => score,
                                        Err(StateError::OverCapacity(_, _)) => i32::MAX,
                                        _ => return None,
                                    };
                                    Some((days, score))
                                })
                                .max_by_key(|&(_, score)| score);
                            let chosen_days = match chosen_days {
                                Some((chosen_days, _)) => chosen_days,
                                None => continue,
                            };

                            match state.insert_order_last(order_id, &chosen_days) {
                                Ok(_) => {
                                    last_location = order_list[&order_id].location_id;
                                    continue 'plan_order;
                                }
                                Err(StateError::OverCapacity(vehicle, day)) => {
                                    // If insertion would cause a segment to fill up then we'll
                                    // simply add a new segment so we can continue to fill up the
                                    // initial solution
                                    let new_segment_index = state.events[vehicle][day].len();
                                    state.execute_operator(
                                        0,
                                        &[
                                            Action::InsertSegment {
                                                vehicle: vehicle,
                                                day: day,
                                                index: new_segment_index,
                                            },
                                        ],
                                    )
                                }
                                _ => (),
                            }
                        }

                        break 'plan_order;
                    }
                }
            }

            // It's possible that some days now end with a new, empty segment. This will cause
            // problems when solving so it has to be removed. If this is the only segment of the day
            // it should *not* be removed, or it won't be possible to insert new orders on that day.
            for vehicle in 0..2 {
                for day in 0..5 {
                    if state.events[vehicle][day]
                        .last()
                        .map(|s| s.is_empty())
                        .unwrap_or(false)
                        && state.events[vehicle][day].len() > 1
                    {
                        state.events[vehicle][day].pop().unwrap();
                    }
                }
            }

            state
        })
        .min_by_key(|state| state.possible_orders.len())
        .unwrap()
}