Dear Julia community this is my third post after my previous post1, post2.
I was unable to replicate my problem in my previous posts. Here, I am going to share my entire algorithm. Please let me know what the problem is.
The algorithm assigns orders to vehicles to minimize the total distance while satisfying the capacity constraints for each vehicle.
Explaining the function definitions
-
function generate_dataCreates coordinates randomly in 2d space for the orders placed by customers and the volume of each order. The first coordinate corresponds to the depot location. -
function maintakes in the generated data and calls switchnumber_of_turnsnumber of times -
function initial_ans!Assigns orders to vehicles in such a way that it satisfies the capacity constraint -
function switch!We take an order from one vehicle and put it into another vehicle and accept the solution based on anif condition
Detailed explanation:
- All the orders locations are indexed from
1:num_of_customers - We declare a matrix
vehicle_stopsof maximum sizenum_of_customers x num_of_vehicles -
function initial_ans!fillsvehicle_stopswith stops. - We randomly select vehicle_pairs randomly without replacement and
function switch!takes an order from one vehicle(one column ofvehicle_stops) and puts it in another vehicle(another column ofvehicle_stops) . For example, if we have 10 vehicles we can do maximum of 5 switches between all the possible pairs.
Our focus is completely on function switch! where the number of switches among all vehicle pairs can be parallelized(one thread for each pair).
Parallel Results with 5 threads
BenchmarkTools.Trial: 1 sample with 1 evaluation.
Single result which took 11.582 s (6.35% GC) to evaluate,
with a memory estimate of 3.84 GiB, over 36451492 allocations.
Serial Results
BenchmarkTools.Trial: 7 samples with 1 evaluation.
Range (min โฆ max): 745.871 ms โฆ 865.928 ms โ GC (min โฆ max): 6.14% โฆ 8.47%
Time (median): 790.421 ms โ GC (median): 8.14%
Time (mean ยฑ ฯ): 804.462 ms ยฑ 45.499 ms โ GC (mean ยฑ ฯ): 7.88% ยฑ 1.18%
โ โ โโ โ โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
746 ms Histogram: frequency by time 866 ms <
Memory estimate: 389.25 MiB, allocs estimate: 5000432.
There is no data race, I included the changes suggested in my previous posts. Can someone please let me know what the problem isโฆ?
Complete code
using DataFrames, DelimitedFiles, Distances, LinearAlgebra, StatsBase, Random, Distributions, Plots, BenchmarkTools, CSV
using FLoops, FoldsThreads, ThreadsX, Revise
###########################################################################
using DataFrames, Distances, LinearAlgebra, Random, Distributions, CSV
using FLoops, FoldsThreads, ThreadsX, Revise
export generate_data, initial_ans!, switch!, main
function generate_data(num_of_customers, num_of_vehicles, max_positions, volume, min_demand_volume, max_demand_volume)
num_of_positions = num_of_customers + 1
positions = Array{Float64,2}(undef, 2, num_of_positions)
foreach(x -> positions[x, :] = sample(0:max_positions, num_of_positions, replace=true), axes(positions, 1))
demand_volume = sample(min_demand_volume:max_demand_volume, num_of_positions, replace=true)
demand_volume[1] = 0
return positions, demand_volume
end
function initial_ans!(num_of_vehicles, num_of_customers, demand_volume, vehicle_stops, vehicles_distances, vehicle_num_stops, vehicles_present_inventory, order_index, distance_matrix)
temp_vehicle_num_stops = deepcopy(vehicle_num_stops)
temp_vehicles_present_inventory = deepcopy(vehicles_present_inventory)
temp_vehicle_stops = deepcopy(vehicle_stops)
@label start_again
for i in 1:num_of_customers
temp = vehicles_present_inventory .- demand_volume[order_index[i]]
free_vehicles = findall(temp .>= 0)
if sizeof(free_vehicles) > 0
chosen_vehicle = rand(free_vehicles)
vehicle_num_stops[chosen_vehicle] = vehicle_num_stops[chosen_vehicle] + 1
vehicles_present_inventory[chosen_vehicle] = vehicles_present_inventory[chosen_vehicle] - demand_volume[order_index[i]]
vehicle_stops[vehicle_num_stops[chosen_vehicle],chosen_vehicle] = i
else
vehicle_num_stops = deepcopy(temp_vehicle_num_stops)
vehicles_present_inventory = deepcopy(temp_vehicles_present_inventory)
vehicle_stops = deepcopy(temp_vehicle_stops)
@goto start_again
end
end
for i in axes(vehicle_stops, 2)
len = vehicle_num_stops[i]
for j in 2:len
vehicles_distances[i] = vehicles_distances[i] + distance_matrix[order_index[vehicle_stops[j-1,i]], order_index[vehicle_stops[j,i]]]
end
#############################################################
if len > 0
vehicles_distances[i] = vehicles_distances[i] + distance_matrix[1, order_index[vehicle_stops[1,i]]]
vehicles_distances[i] = vehicles_distances[i] + distance_matrix[1, order_index[vehicle_stops[len,i]]]
end
#############################################################
end
end
function switch!(random_vehicle_pairs,vehicle_stops_temp, vehicle_stops, vehicles_distances, vehicle_num_stops, vehicles_present_inventory, order_index, volume, demand_volume, distance_matrix, T_c)
vehicle_stops_temp .= vehicle_stops
@floop for idx in axes(random_vehicle_pairs, 2)
truck1 = random_vehicle_pairs[1, idx]
truck2 = random_vehicle_pairs[2, idx]
len1 = vehicle_num_stops[truck1]
len2 = vehicle_num_stops[truck2]
vol1 = vehicles_present_inventory[truck1]
vol2 = vehicles_present_inventory[truck2]
if (len1 > 0)
temp_index = rand(1:len1)
if (vol2 >= demand_volume[order_index[vehicle_stops_temp[temp_index,truck1]]])
temp = vehicle_stops_temp[temp_index,truck1]
for j in temp_index:len1
vehicle_stops_temp[j,truck1] = vehicle_stops_temp[j+1,truck1]
end
len1 = len1 - 1
vol1 = vol1 + demand_volume[order_index[temp]]
temp_index2 = 1
if len2 != 0
temp_index2 = rand(1:len2)
end
for j in len2:-1:temp_index2
vehicle_stops_temp[j+1,truck2] = vehicle_stops_temp[j,truck2]
end
len2 = len2 + 1
vehicle_stops_temp[temp_index2,truck2] = temp
vol2 = vol2 - demand_volume[order_index[temp]]
distance1 = 0.0
for i in 2:len1
distance1 = distance1 + distance_matrix[order_index[vehicle_stops_temp[i-1,truck1]], order_index[vehicle_stops_temp[i,truck1]]]
end
distance2 = 0.0
for i in 2:len2
distance2 = distance2 + distance_matrix[order_index[vehicle_stops_temp[i-1,truck2]], order_index[vehicle_stops_temp[i,truck2]]]
end
##############################################################
if len1 > 0
distance1 = distance1 + distance_matrix[1, order_index[vehicle_stops_temp[1,truck1]]]
distance1 = distance1 + distance_matrix[1, order_index[vehicle_stops_temp[len1,truck1]]]
end
if len2 > 0
distance2 = distance2 + distance_matrix[1, order_index[vehicle_stops_temp[1,truck2]]]
distance2 = distance2 + distance_matrix[1, order_index[vehicle_stops_temp[len2,truck2]]]
end
##############################################################
change = (distance1 + distance2) - (vehicles_distances[truck1] + vehicles_distances[truck2])
if rand() <= min(1, exp(-(change / T_c)))
vehicle_num_stops[truck1] = len1
vehicle_num_stops[truck2] = len2
vehicles_present_inventory[truck1] = vol1
vehicles_present_inventory[truck2] = vol2
vehicle_stops[1:len1+1, truck1] .= @view(vehicle_stops_temp[1:len1+1,truck1])
vehicle_stops[1:len2, truck2] .= @view(vehicle_stops_temp[1:len2,truck2])
vehicles_distances[truck1] = distance1
vehicles_distances[truck2] = distance2
end
end
end
end
end
function main(number_of_turns, T_i, num_of_vehicles, num_of_customers, volume, positions, demand_volume, number_of_switches)
################# Declaring the Truck Variables#############################
vehicle_stops = -ones(Int64, num_of_customers, num_of_vehicles)
vehicles_distances = zeros(Float64, num_of_vehicles)
vehicle_num_stops = zeros(Int, num_of_vehicles)
vehicles_present_inventory = fill(volume, num_of_vehicles)
order_index = collect(1:num_of_customers) .+ 1
########Calculating Distance Matrix####################
distance_matrix = Symmetric(pairwise(Euclidean(), positions, dims=2))
################Creating Initial Solution###################################
initial_ans!(num_of_vehicles, num_of_customers, demand_volume, vehicle_stops, vehicles_distances, vehicle_num_stops, vehicles_present_inventory, order_index, distance_matrix)
################Annealing Parameters########################################
T_f = 0
T_c = T_i
costs = zeros(AbstractFloat, number_of_turns)
ฮณ = (T_i - T_f) / number_of_turns
################Loop###########################################
vehicle_stops2 = deepcopy(vehicle_stops)
println("Solver Started")
for j in 1:number_of_turns
random_vehicle_pairs = reshape(sample(1:num_of_vehicles, number_of_switches * 2; replace=false), 2, number_of_switches)
switch!(random_vehicle_pairs, vehicle_stops2, vehicle_stops, vehicles_distances, vehicle_num_stops, vehicles_present_inventory, order_index, volume, demand_volume, distance_matrix, T_c)
T_c = T_c - ฮณ
costs[j] = sum(vehicles_distances)
end
return costs, vehicle_num_stops, vehicle_stops
end
################Reading Data###############################################
num_of_customers :: Int =100
num_of_vehicles :: Int = 10
max_positions :: Int = 100
volume :: Int = 100
min_demand_volume, max_demand_volume = 1, 10
positions, demand_volume = generate_data(num_of_customers, num_of_vehicles, max_positions, volume, min_demand_volume, max_demand_volume)
###########Input Parameters####################################
number_of_turns::Int = 1000000
T_i::Int = 15
number_of_switches = floor(Int, num_of_vehicles / 2)
##############################################################
@benchmark begin
costs, vehicle_num_stops, vehicle_stops = main(number_of_turns, T_i, num_of_vehicles, num_of_customers, volume, positions, demand_volume, number_of_switches)
end