文章目录[隐藏]
WordPress柔性供应链中的智能路径优化算法实现教程
引言：柔性供应链与路径优化的融合
在当今电子商务快速发展的时代，WordPress作为全球最流行的内容管理系统，已成为众多电商企业的首选平台。随着供应链复杂性的增加，传统的固定路径配送模式已无法满足现代商业需求。柔性供应链通过动态调整物流路径、库存分配和配送策略，能够显著提升运营效率并降低成本。
本文将详细介绍如何在WordPress环境中实现智能路径优化算法，帮助电商企业构建更加灵活高效的供应链系统。我们将从基础概念入手，逐步深入到算法实现和代码部署。
一、智能路径优化算法基础
1.1 路径优化问题定义
路径优化问题（Vehicle Routing Problem, VRP）是供应链管理中的核心问题之一，旨在为多个配送车辆找到最优的配送路线，以最小化总运输成本或最大化服务效率。
1.2 常用优化算法比较
- 遗传算法：模拟自然选择过程，适合解决复杂优化问题
- 模拟退火算法：基于物理退火过程，避免陷入局部最优解
- 蚁群算法：模拟蚂蚁觅食行为，适合动态路径规划
- Dijkstra算法：经典的最短路径算法，适合静态网络
二、WordPress环境准备与配置
2.1 系统要求检查
在开始之前，请确保您的WordPress环境满足以下要求：
- PHP 7.4或更高版本
- MySQL 5.7或更高版本
- 至少256MB内存限制
- 启用curl和json扩展
2.2 创建自定义插件框架
首先，我们需要创建一个WordPress插件来承载我们的路径优化功能：
<?php
/**
* Plugin Name: 智能路径优化系统
* Plugin URI: https://yourwebsite.com/
* Description: WordPress柔性供应链智能路径优化解决方案
* Version: 1.0.0
* Author: 您的名称
* License: GPL v2 or later
*/
// 防止直接访问
if (!defined('ABSPATH')) {
exit;
}
// 定义插件常量
define('SRO_PLUGIN_DIR', plugin_dir_path(__FILE__));
define('SRO_PLUGIN_URL', plugin_dir_url(__FILE__));
// 初始化插件
class SmartRouteOptimizer {
public function __construct() {
$this->init_hooks();
}
private function init_hooks() {
// 注册激活和停用钩子
register_activation_hook(__FILE__, array($this, 'activate'));
register_deactivation_hook(__FILE__, array($this, 'deactivate'));
// 添加管理菜单
add_action('admin_menu', array($this, 'add_admin_menu'));
// 加载脚本和样式
add_action('admin_enqueue_scripts', array($this, 'enqueue_admin_assets'));
}
public function activate() {
// 创建必要的数据库表
$this->create_database_tables();
// 初始化默认设置
$this->initialize_default_settings();
}
public function deactivate() {
// 清理临时数据
$this->cleanup_temporary_data();
}
// 其他方法将在后续章节实现
}
// 初始化插件
$smart_route_optimizer = new SmartRouteOptimizer();
?>三、遗传算法在路径优化中的实现
3.1 遗传算法核心类实现
<?php
/**
* 遗传算法路径优化类
*/
class GeneticRouteOptimizer {
private $population_size;
private $mutation_rate;
private $crossover_rate;
private $max_generations;
private $locations = array();
private $distance_matrix = array();
/**
* 构造函数
* @param array $locations 配送点数组
* @param int $population_size 种群大小
* @param float $mutation_rate 变异率
* @param float $crossover_rate 交叉率
* @param int $max_generations 最大迭代次数
*/
public function __construct($locations, $population_size = 100,
$mutation_rate = 0.01, $crossover_rate = 0.8,
$max_generations = 1000) {
$this->locations = $locations;
$this->population_size = $population_size;
$this->mutation_rate = $mutation_rate;
$this->crossover_rate = $crossover_rate;
$this->max_generations = $max_generations;
// 计算距离矩阵
$this->calculate_distance_matrix();
}
/**
* 计算距离矩阵
*/
private function calculate_distance_matrix() {
$count = count($this->locations);
for ($i = 0; $i < $count; $i++) {
for ($j = 0; $j < $count; $j++) {
if ($i == $j) {
$this->distance_matrix[$i][$j] = 0;
} else {
$this->distance_matrix[$i][$j] = $this->calculate_distance(
$this->locations[$i]['lat'],
$this->locations[$i]['lng'],
$this->locations[$j]['lat'],
$this->locations[$j]['lng']
);
}
}
}
}
/**
* 计算两点间距离（使用Haversine公式）
* @param float $lat1 纬度1
* @param float $lng1 经度1
* @param float $lat2 纬度2
* @param float $lng2 经度2
* @return float 距离（公里）
*/
private function calculate_distance($lat1, $lng1, $lat2, $lng2) {
$earth_radius = 6371; // 地球半径，单位公里
$lat1_rad = deg2rad($lat1);
$lat2_rad = deg2rad($lat2);
$delta_lat = deg2rad($lat2 - $lat1);
$delta_lng = deg2rad($lng2 - $lng1);
$a = sin($delta_lat/2) * sin($delta_lat/2) +
cos($lat1_rad) * cos($lat2_rad) *
sin($delta_lng/2) * sin($delta_lng/2);
$c = 2 * atan2(sqrt($a), sqrt(1-$a));
return $earth_radius * $c;
}
/**
* 初始化种群
* @return array 初始种群
*/
private function initialize_population() {
$population = array();
$num_locations = count($this->locations);
for ($i = 0; $i < $this->population_size; $i++) {
// 创建随机路径（0为仓库，其他为配送点）
$route = range(1, $num_locations - 1);
shuffle($route);
array_unshift($route, 0); // 仓库作为起点
$route[] = 0; // 返回仓库
$population[] = array(
'route' => $route,
'fitness' => 0
);
}
return $population;
}
/**
* 计算路径适应度（总距离的倒数）
* @param array $route 路径数组
* @return float 适应度值
*/
private function calculate_fitness($route) {
$total_distance = 0;
$route_length = count($route);
for ($i = 0; $i < $route_length - 1; $i++) {
$from = $route[$i];
$to = $route[$i + 1];
$total_distance += $this->distance_matrix[$from][$to];
}
// 适应度为总距离的倒数（距离越短，适应度越高）
return 1 / ($total_distance + 1);
}
/**
* 选择操作（轮盘赌选择）
* @param array $population 当前种群
* @return array 被选中的个体
*/
private function selection($population) {
$total_fitness = array_sum(array_column($population, 'fitness'));
$selected = array();
for ($i = 0; $i < 2; $i++) {
$random_point = mt_rand() / mt_getrandmax() * $total_fitness;
$current_sum = 0;
foreach ($population as $individual) {
$current_sum += $individual['fitness'];
if ($current_sum >= $random_point) {
$selected[] = $individual;
break;
}
}
}
return $selected;
}
/**
* 交叉操作（顺序交叉）
* @param array $parent1 父代1
* @param array $parent2 父代2
* @return array 两个子代
*/
private function crossover($parent1, $parent2) {
if (mt_rand() / mt_getrandmax() > $this->crossover_rate) {
return array($parent1, $parent2);
}
$route_length = count($parent1['route']);
$cut_point1 = rand(1, $route_length - 3);
$cut_point2 = rand($cut_point1 + 1, $route_length - 2);
// 创建子代
$child1 = $this->create_child($parent1, $parent2, $cut_point1, $cut_point2);
$child2 = $this->create_child($parent2, $parent1, $cut_point1, $cut_point2);
return array(
array('route' => $child1, 'fitness' => 0),
array('route' => $child2, 'fitness' => 0)
);
}
/**
* 创建子代个体
*/
private function create_child($parent1, $parent2, $start, $end) {
$child = array_fill(0, count($parent1['route']), -1);
// 复制父代1的片段
for ($i = $start; $i <= $end; $i++) {
$child[$i] = $parent1['route'][$i];
}
// 从父代2填充剩余位置
$child_index = ($end + 1) % count($child);
foreach ($parent2['route'] as $gene) {
if ($gene == 0) continue; // 跳过仓库
if (!in_array($gene, $child)) {
while ($child[$child_index] != -1) {
$child_index = ($child_index + 1) % count($child);
}
$child[$child_index] = $gene;
}
}
// 填充剩余的-1位置
for ($i = 0; $i < count($child); $i++) {
if ($child[$i] == -1) {
$child[$i] = 0; // 仓库位置
}
}
return $child;
}
/**
* 变异操作（交换变异）
* @param array $individual 个体
* @return array 变异后的个体
*/
private function mutation($individual) {
if (mt_rand() / mt_getrandmax() > $this->mutation_rate) {
return $individual;
}
$route = $individual['route'];
$route_length = count($route);
// 选择两个非仓库位置进行交换
$pos1 = rand(1, $route_length - 2);
$pos2 = rand(1, $route_length - 2);
while ($pos1 == $pos2 || $route[$pos1] == 0 || $route[$pos2] == 0) {
$pos1 = rand(1, $route_length - 2);
$pos2 = rand(1, $route_length - 2);
}
// 交换位置
$temp = $route[$pos1];
$route[$pos1] = $route[$pos2];
$route[$pos2] = $temp;
return array('route' => $route, 'fitness' => 0);
}
/**
* 执行遗传算法优化
* @return array 最优路径
*/
public function optimize() {
// 初始化种群
$population = $this->initialize_population();
// 计算初始适应度
foreach ($population as &$individual) {
$individual['fitness'] = $this->calculate_fitness($individual['route']);
}
$best_individual = null;
$best_fitness = 0;
// 主循环
for ($generation = 0; $generation < $this->max_generations; $generation++) {
$new_population = array();
// 保留最优个体（精英策略）
usort($population, function($a, $b) {
return $b['fitness'] <=> $a['fitness'];
});
$new_population[] = $population[0];
// 生成新一代
while (count($new_population) < $this->population_size) {
// 选择
$parents = $this->selection($population);
// 交叉
$children = $this->crossover($parents[0], $parents[1]);
// 变异
foreach ($children as $child) {
$mutated_child = $this->mutation($child);
$mutated_child['fitness'] = $this->calculate_fitness($mutated_child['route']);
$new_population[] = $mutated_child;
if (count($new_population) >= $this->population_size) {
break;
}
}
}
$population = $new_population;
// 更新最优解
foreach ($population as $individual) {
if ($individual['fitness'] > $best_fitness) {
$best_fitness = $individual['fitness'];
$best_individual = $individual;
}
}
// 输出进度（每100代）
if ($generation % 100 == 0) {
$best_distance = 1 / $best_fitness - 1;
error_log("Generation {$generation}: Best distance = " . round($best_distance, 2) . " km");
}
}
return $best_individual;
}
}
?>四、WordPress集成与前端展示
4.1 创建管理页面和短代码
<?php
/**
* 路径优化管理类
*/
class RouteOptimizationManager {
/**
* 添加管理菜单
*/
public function add_admin_menu() {
add_menu_page(
'智能路径优化',
'路径优化',
'manage_options',
'smart-route-optimizer',
array($this, 'render_admin_page'),
'dashicons-location-alt',
30
);
}
/**
* 渲染管理页面
*/
public function render_admin_page() {
?>
<div class="wrap">
<h1>智能路径优化系统</h1>
<div class="sro-container">
<div class="sro-control-panel">
<h2>路径优化控制面板</h2>
<form method="post" action="">
<?php wp_nonce_field('sro_optimize_route', 'sro_nonce'); ?>
<div class="form-group">
<label for="locations">配送点数据（JSON格式）:</label>
<textarea id="locations" name="locations" rows="10" cols="50">
[
{"id": 0, "name": "中央仓库", "lat": 31.2304, "lng": 121.4737, "address": "上海市中心"},
{"id": 1, "name": "客户A", "lat": 31.2242, "lng": 121.4697, "address": "上海市黄浦区"},
{"id": 2, "name": "客户B", "lat": 31.2200, "lng": 121.4800, "address": "上海市静安区"},
{"id": 3, "name": "客户C", "lat": 31.2400, "lng": 121.4900, "address": "上海市虹口区"},
{"id": 4, "name": "客户D", "lat": 31.2100, "lng": 121.4700, "address": "上海市徐汇区"}
]
</textarea>
</div>
<div class="form-group">
<label for="population_size">种群大小:</label>
<input type="number" id="population_size" name="population_size" value="100" min="10" max="1000">
</div>
<div class="form-group">
<label for="max_generations">最大迭代次数:</label>
<input type="number" id="max_generations" name="max_generations" value="1000" min="100" max="10000">
</div>
<input type="submit" name="optimize" class="button button-primary" value="开始优化">
</form>
<?php
if (isset($_POST['optimize']) && wp_verify_nonce($_POST['sro_nonce'], 'sro_optimize_route')) {
$this->process_optimization();
}
?>
</div>
<div class="sro-results">
<h2>优化结果</h2>
<div id="optimization-results">
<!-- 结果将通过AJAX加载 -->
</div>
</div>
</div>
</div>
<style>
.sro-container {
display: flex;
gap: 20px;
margin-top: 20px;
}
.sro-control-panel {
flex: 1;background: #fff;
padding: 20px;
border-radius: 5px;
box-shadow: 0 2px 4px rgba(0,0,0,0.1);
}
.sro-results {
flex: 2;
background: #fff;
padding: 20px;
border-radius: 5px;
box-shadow: 0 2px 4px rgba(0,0,0,0.1);
}
.form-group {
margin-bottom: 15px;
}
.form-group label {
display: block;
margin-bottom: 5px;
font-weight: bold;
}
.form-group textarea,
.form-group input[type="number"] {
width: 100%;
padding: 8px;
border: 1px solid #ddd;
border-radius: 4px;
}
.route-visualization {
margin-top: 20px;
padding: 15px;
background: #f8f9fa;
border-radius: 4px;
}
</style>
<script>
jQuery(document).ready(function($) {
// 如果提交了优化请求，通过AJAX获取结果
<?php if (isset($_POST['optimize'])): ?>
fetchOptimizationResults();
<?php endif; ?>
function fetchOptimizationResults() {
$.ajax({
url: '<?php echo admin_url('admin-ajax.php'); ?>',
type: 'POST',
data: {
action: 'sro_get_optimization_results',
nonce: '<?php echo wp_create_nonce('sro_ajax_nonce'); ?>'
},
success: function(response) {
if (response.success) {
$('#optimization-results').html(response.data.html);
if (response.data.map_html) {
$('#optimization-results').append(response.data.map_html);
}
}
}
});
}
});
</script>
<?php
}
/**
* 处理优化请求
*/
private function process_optimization() {
$locations = json_decode(stripslashes($_POST['locations']), true);
$population_size = intval($_POST['population_size']);
$max_generations = intval($_POST['max_generations']);
if (!$locations) {
echo '<div class="notice notice-error"><p>无效的配送点数据格式</p></div>';
return;
}
// 创建优化器实例
$optimizer = new GeneticRouteOptimizer(
$locations,
$population_size,
0.01, // 变异率
0.8, // 交叉率
$max_generations
);
// 执行优化
$start_time = microtime(true);
$result = $optimizer->optimize();
$execution_time = microtime(true) - $start_time;
// 保存结果到临时选项
update_option('sro_last_optimization', array(
'result' => $result,
'locations' => $locations,
'execution_time' => $execution_time,
'timestamp' => current_time('mysql')
));
echo '<div class="notice notice-success"><p>路径优化完成！耗时：'
. round($execution_time, 2) . '秒</p></div>';
}
/**
* 注册AJAX处理函数
*/
public function register_ajax_handlers() {
add_action('wp_ajax_sro_get_optimization_results', array($this, 'ajax_get_results'));
add_action('wp_ajax_nopriv_sro_get_optimization_results', array($this, 'ajax_get_results'));
}
/**
* AJAX获取优化结果
*/
public function ajax_get_results() {
check_ajax_referer('sro_ajax_nonce', 'nonce');
$last_optimization = get_option('sro_last_optimization');
if (!$last_optimization) {
wp_send_json_error('没有找到优化结果');
}
$result = $last_optimization['result'];
$locations = $last_optimization['locations'];
// 计算总距离
$total_distance = 0;
$optimizer = new GeneticRouteOptimizer($locations);
$reflection = new ReflectionClass($optimizer);
$method = $reflection->getMethod('calculate_distance');
$method->setAccessible(true);
$route = $result['route'];
for ($i = 0; $i < count($route) - 1; $i++) {
$from_loc = $locations[$route[$i]];
$to_loc = $locations[$route[$i + 1]];
$total_distance += $method->invokeArgs($optimizer, array(
$from_loc['lat'], $from_loc['lng'],
$to_loc['lat'], $to_loc['lng']
));
}
// 生成结果HTML
$html = '<div class="route-details">';
$html .= '<h3>最优路径详情</h3>';
$html .= '<p><strong>总距离：</strong>' . round($total_distance, 2) . ' 公里</p>';
$html .= '<p><strong>路径顺序：</strong></p>';
$html .= '<ol>';
foreach ($route as $index => $location_idx) {
$loc = $locations[$location_idx];
$html .= '<li>' . esc_html($loc['name']) . ' (' . $loc['address'] . ')</li>';
}
$html .= '</ol>';
$html .= '</div>';
// 生成地图可视化HTML
$map_html = $this->generate_map_html($route, $locations);
wp_send_json_success(array(
'html' => $html,
'map_html' => $map_html
));
}
/**
* 生成地图可视化HTML
*/
private function generate_map_html($route, $locations) {
$map_locations = array();
foreach ($route as $loc_idx) {
$loc = $locations[$loc_idx];
$map_locations[] = array(
'name' => $loc['name'],
'lat' => $loc['lat'],
'lng' => $loc['lng'],
'address' => $loc['address']
);
}
ob_start();
?>
<div class="route-visualization">
<h3>路径可视化</h3>
<div id="route-map" style="height: 400px; width: 100%;"></div>
<script>
jQuery(document).ready(function($) {
// 初始化地图
var map = L.map('route-map').setView([<?php echo $locations[0]['lat']; ?>, <?php echo $locations[0]['lng']; ?>], 13);
// 添加地图图层
L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
attribution: '© OpenStreetMap contributors'
}).addTo(map);
// 添加路径点
var locations = <?php echo json_encode($map_locations); ?>;
var routePoints = [];
locations.forEach(function(location, index) {
var marker = L.marker([location.lat, location.lng])
.addTo(map)
.bindPopup('<b>' + location.name + '</b><br>' + location.address);
routePoints.push([location.lat, location.lng]);
// 添加序号标签
L.divIcon({
className: 'route-number',
html: '<div style="background: white; border-radius: 50%; width: 24px; height: 24px; text-align: center; line-height: 24px; border: 2px solid #0073aa;">' + (index + 1) + '</div>',
iconSize: [24, 24]
}).addTo(map).setLatLng([location.lat, location.lng]);
});
// 绘制路径线
L.polyline(routePoints, {
color: '#0073aa',
weight: 3,
opacity: 0.7
}).addTo(map);
// 调整地图视图以显示所有点
map.fitBounds(routePoints);
});
</script>
<link rel="stylesheet" href="https://unpkg.com/leaflet@1.7.1/dist/leaflet.css" />
<script src="https://unpkg.com/leaflet@1.7.1/dist/leaflet.js"></script>
<style>
.route-number {
background: none !important;
border: none !important;
}
</style>
</div>
<?php
return ob_get_clean();
}}
?>
## 五、数据库设计与数据持久化
### 5.1 创建供应链相关数据表
<?php
/**
- 数据库管理类
*/
class SRO_Database {
/**
* 创建数据库表
*/
public static function create_tables() {
global $wpdb;
$charset_collate = $wpdb->get_charset_collate();
// 配送点表
$locations_table = $wpdb->prefix . 'sro_locations';
$sql_locations = "CREATE TABLE IF NOT EXISTS $locations_table (
id mediumint(9) NOT NULL AUTO_INCREMENT,
name varchar(100) NOT NULL,
address text NOT NULL,
lat decimal(10,8) NOT NULL,
lng decimal(11,8) NOT NULL,
priority tinyint(1) DEFAULT 0,
time_window_start time DEFAULT NULL,
time_window_end time DEFAULT NULL,
created_at datetime DEFAULT CURRENT_TIMESTAMP,
PRIMARY KEY (id)
) $charset_collate;";
// 配送车辆表
$vehicles_table = $wpdb->prefix . 'sro_vehicles';
$sql_vehicles = "CREATE TABLE IF NOT EXISTS $vehicles_table (
id mediumint(9) NOT NULL AUTO_INCREMENT,
vehicle_name varchar(100) NOT NULL,
capacity decimal(10,2) DEFAULT 0,
operating_cost decimal(10,2) DEFAULT 0,
avg_speed decimal(5,2) DEFAULT 40,
is_active tinyint(1) DEFAULT 1,
PRIMARY KEY (id)
) $charset_collate;";
// 优化历史表
$history_table = $wpdb->prefix . 'sro_optimization_history';
$sql_history = "CREATE TABLE IF NOT EXISTS $history_table (
id mediumint(9) NOT NULL AUTO_INCREMENT,
route_data longtext NOT NULL,
total_distance decimal(10,2) NOT NULL,
total_cost decimal(10,2) NOT NULL,
vehicle_count int NOT NULL,
execution_time decimal(5,2) NOT NULL,
optimized_at datetime DEFAULT CURRENT_TIMESTAMP,
parameters text,
PRIMARY KEY (id),
KEY optimized_at (optimized_at)
) $charset_collate;";
require_once(ABSPATH . 'wp-admin/includes/upgrade.php');
dbDelta($sql_locations);
dbDelta($sql_vehicles);
dbDelta($sql_history);
// 插入示例数据
self::insert_sample_data();
}
/**
* 插入示例数据
*/
private static function insert_sample_data() {
global $wpdb;
$locations_table = $wpdb->prefix . 'sro_locations';
// 检查是否已有数据
$count = $wpdb->get_var("SELECT COUNT(*) FROM $locations_table");
if ($count == 0) {
$sample_locations = array(
array('中央仓库', '上海市中心', 31.2304, 121.4737),
array('客户A', '上海市黄浦区', 31.2242, 121.4697),
array('客户B', '上海市静安区', 31.2200, 121.4800),
array('客户C', '上海市虹口区', 31.2400, 121.4900),
array('客户D', '上海市徐汇区', 31.2100, 121.4700)
);
foreach ($sample_locations as $location) {
$wpdb->insert(
$locations_table,
array(
'name' => $location[0],
'address' => $location[1],
'lat' => $location[2],
'lng' => $location[3]
)
);
}
}
}
/**
* 保存优化结果到数据库
*/
public static function save_optimization_result($data) {
global $wpdb;
$history_table = $wpdb->prefix . 'sro_optimization_history';
return $wpdb->insert(
$history_table,
array(
'route_data' => json_encode($data['route_data'], JSON_UNESCAPED_UNICODE),
'total_distance' => $data['total_distance'],
'total_cost' => $data['total_cost'],
'vehicle_count' => $data['vehicle_count'],
'execution_time' => $data['execution_time'],
'parameters' => json_encode($data['parameters'])
)
);
}
/**
* 获取优化历史
*/
public static function get_optimization_history($limit = 10) {
global $wpdb;
$history_table = $wpdb->prefix . 'sro_optimization_history';
return $wpdb->get_results(
$wpdb->prepare(
"SELECT * FROM $history_table ORDER BY optimized_at DESC LIMIT %d",
$limit
)
);
}}
?>
## 六、高级功能扩展
### 6.1 多车辆路径优化
<?php
/**
- 多车辆路径优化扩展
*/
class MultiVehicleRouteOptimizer extends GeneticRouteOptimizer {
private $vehicle_count;
private $vehicle_capacities;
private $location_demands;
/**
* 扩展构造函数
*/
public function __construct($locations, $vehicle_count = 3, $vehicle_capacities = array(),
$location_demands = array(), $population_size = 100,
$mutation_rate = 0.01, $crossover_rate = 0.8,
$max_generations = 1000) {
parent::__construct($locations, $population_size, $mutation_rate,
$crossover_rate, $max_generations);
$this->vehicle_count = $vehicle_count;
$this->vehicle_capacities = $vehicle_capacities;
$this->location_demands = $location_demands;
}
/**
* 重写初始化种群方法，支持多车辆
*/
protected function initialize_population() {
$population = array();
$num_locations = count($this->locations);
for ($i = 0; $i < $this->population_size; $i++) {
// 生成多车辆路径
$routes = $this->generate_multi_vehicle_route();
$population[] = array(
'routes' => $routes,
'fitness' => 0
);
}
return $population;
}
/**
* 生成多车辆路径
*/
private function generate_multi_vehicle_route() {
$num_customers = count($this->locations) - 1;
$customers = range(1, $num_customers);
shuffle($customers);
$routes = array();
$current_route = array(0); // 从仓库开始
foreach ($customers as $customer) {
$current_route[] = $customer;
// 检查容量约束
if ($this->check_capacity_constraint($current_route)) {
continue;
} else {
// 移除最后一个客户，开始新路线
array_pop($current_route);
$current_route[] = 0; // 返回仓库
$routes[] = $current_route;
// 开始新路线
$current_route = array(0, $customer);
}
}
// 添加最后一条路线
if (count($current_route) > 1) {
$current_route[] = 0;
$routes[] = $current_route;
}
// 如果路线数量超过车辆数，需要合并
while (count($routes) > $this->vehicle_count) {
$routes = $this->merge_routes($routes);
}
return $routes;
}
/**
* 检查容量约束
*/
private function check_capacity_constraint($route) {
if (empty($this->vehicle_capacities) || empty($this->location_demands)) {
return true; // 没有容量约束
}
$total_demand = 0;
foreach ($route as $location_idx) {
if ($location_idx > 0 && isset($this->location_demands[$location_idx])) {
$total_demand += $this->location_demands[$location_idx];
}
}
return $total_demand <= $this->vehicle_capacities[0]; // 假设所有车辆容量相同
}
/**
* 合并路线
*/
private function merge_routes($routes) {
// 找到最短的两条路线进行合并
$min_distance = PHP_INT_MAX;
$merge_index1 = 0;
$merge_index2 = 1;
for ($i = 0; $i < count($routes); $i++) {
for ($j = $i + 1; $j < count($routes); $j++) {
$merged_route = array_merge(
array_slice($routes[$i], 0, -1), // 移除第一个路线的结束仓库
array_slice($routes[$j], 1) // 移除第二个路线的开始仓库