3

I am making a scheduler for truck rides that minimizes the total costs of driving by reducing deadhead. There are two phases in my program: making an initial planning and optimizing the planning. The planning is currently saved as a Dictionary<Truck, List <Trip>>. Here each truck has to drive all trips in the order of the list of trips. The sequence of the trips is the same as the sequence of the list.

An initial schedule is created using Munkres’ algorithm on different phases of deadlines. If the initial schedule is ready, it will be optimized by an evolving genetic algorithm. In the GA a lot of threads try to improve the schedule. A thread can work follows:

  1. Get the current schedule.
  2. Randomly change the sequence of trips for a truck or change the distribution of trips to trucks.
  3. Check if deadlines are still made in the modified schedule. If not start at 1 again, otherwise go on.
  4. Check if costs of schedule are reduced by modification. If not start at 1 again, otherwise go on.
  5. Set/Merge/Change the schedule.

Step 3 and 4 are very expensive operations (can take more than 500ms). I thought about saving the schedule as an ImmutableDictionary instead of a Dictionary, so that after step 1 to the working schedule will not be changed by other threads. Then the problem is: How to do step 5. Any idea how I can handle this well? Or should I do it in another way than the ImmutableDictionary idea?

Making it more general: What is a good way to merge a Dictionary that other threads are also working with?

J. Overeem
  • 53
  • 4
  • 4
    What about `ConcurrentDictionary` (https://msdn.microsoft.com/en-us/library/dd287191(v=vs.110).aspx)? – Dovydas Šopa Apr 21 '16 at 11:00
  • In `ConcurrentDictionary` I find methods to fix concurrency issues related to the presence of a key, but these will not solve my problem. If a thread changes a sequence of trips `{t3,t8,t2,t6}` into `{t3,t2,t8,t6}` while another thread already changed the sequence into `{t8,t3,t2,t6}`, it is an issue. This is not solved by using a `ConcurrentDictionary`. Also not by using `ConcurrentList`s because trips can be changed between different lists too. Any other thoughts? – J. Overeem Apr 21 '16 at 12:27
  • Well, if order is important, then why are you using `Dictionary` at all? "The order of elements in a dictionary is non-deterministic" - http://stackoverflow.com/questions/4007782/the-order-of-elements-in-dictionary – Dovydas Šopa Apr 21 '16 at 12:35
  • The order of the `Dictionary` is not important. The order of the `List` is. As I said, the trips are driven in the order of the list. So the `Dictionary` is to connect a truck to a `list`/sequence of trips. The order of the list can be changed (changing order of trips), and trips can be moved to a list that is connected to another truck (assigning to another truck). – J. Overeem Apr 21 '16 at 12:49
  • Well.. I would say that each of the GA threads should have its own copy of your data structure. After each cycle you change your base data structure with the best one found by GA and then send its copies for another iteration. – Dovydas Šopa Apr 21 '16 at 13:03
  • That requires that all threads run in the same cycle blocks instead of continuously, and all improvements that are not the best one will be omitted each cycle. That is not what I am looking for, but the cycle idea might work if no other answers come up. – J. Overeem Apr 21 '16 at 13:20

1 Answers1

1

This sounds like a case where you'd benefit from using the ConcurrentDictionary detailed here on MSDN. This was called out by a commentator already, but nonetheless -- still deserves to be formally stated.

You can use the this in conjunction with Lazy<T> for some extremely powerful and thread-safe code. Checkout this article on using both together. Here is a .NET Fiddle detailing its usage.

static readonly ConcurrentDictionary<Guid, Lazy<T>> MostRecentData =
            new ConcurrentDictionary<Guid, Lazy<T>>();

Then you can walk up to the MostRecentData variable and invoke its methods, like .AddOrUpdate, etc. This one specifically takes two factory lambdas which evaluate an addition to the dictionary and an update if the key was already present.

David Pine
  • 23,787
  • 10
  • 79
  • 107