解桂林四日游设计最优旅游路线的整数规划

记录沟槽的生活.

题目建模

对于下文的表示，默认所有变量在合理区间内. 并且 等价于

决策变量 令 中 表示在第 天选择去景点 游玩.

其中：

•  = 游玩天数，（从第一天开始记为 ，随后依次递增）；
•  = 景点编号，（对应：0 = 象鼻山，1 = 漓江，2 = 阳朔西街，3 = 遇龙河，4 = 十里画廊，5 = 银子岩，6 = 龙脊梯田，7 = 靖江王城，8 = 两江四湖）；

令 矩阵，，其中：

• ​：景点的游玩时间（小时）
• ：景点的门票 / 项目费用（元）
• ：景点的兴趣度

约束条件 需要满足以下约束：

• 次数约束： 仅为 或 并且
• 时间约束：
• 费用约束：
• 地理约束：
  • .

优化目标

使总兴趣度最大，即：

代码：

import pulp as lp  
import numpy as np  
  
# ===================== 工具函数 ====================  
  
NAME_DICT = {  
    0: "象鼻山", 1: "漓江", 2: "阳朔西街", 3: "遇龙河", 4: "十里画廊",  
    5: "银子岩", 6: "龙脊梯田", 7: "靖江王城", 8: "两江四湖"  
}  
  
  
def idx_to_name(idx):  
    return NAME_DICT[idx]  
  
  
# ===================== 导入数据 ====================  
NUM_DAYS = 3  
A = [  
    [1.5, 60, 8],  
    [4.5, 250, 10],  
    [2, 0, 7],  
    [2, 180, 9],  
    [3, 40, 8],  
    [2, 80, 7],  
    [8, 100, 9],  
    [2.5, 120, 6],  
    [1.5, 180, 8],  
]  
  
A = np.asarray(A)  
  
NUM_POINTS = A.shape[0]  
  
print(A)  
  
print(f'共有{NUM_POINTS}个景点, 需要游玩{NUM_DAYS}天')  
  
# ===================== 建模 ====================  
  
prob = lp.LpProblem("GuilinTravelOptProb", lp.LpMaximize)  
  
X = {}  
for i in range(NUM_DAYS):  
    for j in range(NUM_POINTS):  
        X[(i, j)] = lp.LpVariable(f'x_{i}_{j}', 0, 1, lp.LpBinary)  
  
## 添加目标  
prob += lp.lpSum([X[(i, j)] * A[j][2] for i in range(NUM_DAYS) for j in range(NUM_POINTS)]), "total s"  
  
##  添加约束  
  
# 次数约束  
for j in range(NUM_POINTS):  
    prob += lp.lpSum([X[(i, j)] for i in range(NUM_DAYS)]) <= 1  
  
# 时间约束  
for i in range(NUM_DAYS):  
    prob += lp.lpSum([X[(i, j)] * A[j][0] for j in range(NUM_POINTS)]) <= 10  
  
# 费用约束  
prob += lp.lpSum([X[(i, j)] * A[j][1] for i in range(NUM_DAYS) for j in range(NUM_POINTS)]) <= 800  
  
# 地理约束  
for i in range(NUM_DAYS):  
    prob += lp.lpSum([X[(i, j)] for j in range(NUM_POINTS)]) <= 1 + NUM_POINTS * (1 - X[(i, 6)])  
  
for i in range(NUM_DAYS):  
    prob += lp.lpSum([X[(i, j)] for j in range(2, 6)]) >= X[(i, 1)]  
    prob += lp.lpSum([X[(i, 0)]]) <= 1 - X[(i, 1)]  
    prob += lp.lpSum([X[(i, 7)]]) <= 1 - X[(i, 1)]  
  
# ===================== 求解 ====================  
  
prob.solve(lp.PULP_CBC_CMD(msg=False))  # 用编译的 cbc 求解器  
  
print("== 求解结果 ==")  
print(f"求解状态：{lp.LpStatus[prob.status]}")  
print(f"最大总兴趣度：{lp.value(prob.objective):.0f}")  
  
# 统计总数据  
total_cost = 0  
total_time = 0  
total_s = 0  
  
# 输出每天行程  
for i in range(NUM_DAYS):  
    selected_j = [j for j in range(NUM_POINTS) if X[(i, j)].varValue == 1]  
    selected_names = [idx_to_name(j) for j in selected_j]  
  
    # 计算当天费用  
    day_cost = sum([A[j][1] for j in selected_j])  
    total_cost += day_cost  
    total_time += sum([A[j][0] for j in selected_j])  
    total_s += sum([A[j][2] for j in selected_j])  
  
    # 计算当天游玩时间  
    day_time = sum([A[j][0] for j in selected_j])  
    print(f"\n第{i + 1}天：")  
    print(f"  游玩景点：{selected_names}")  
    print(f"  游玩时间：{day_time}小时 | 当天费用：{day_cost}元 | 兴趣度： {total_s}")  
  
print(f"总用时：{total_time} 小时 | 总费用：{total_cost}元 | 总兴趣度：{total_s}")