Abstract: The region in which China imports the most crude oil is the Middle East. And the ocean shipping scale of crude oil along Middle East-China transportation route also increases. To save the ocean shipping cost effectively and cut down the primary logistics cost, the characteristics of ocean shipping of crude oil along the Middle East-China transportation route were analyzed, and an optimization model of transportation scheme was established. The optimization of ocean shipping scheme of crude oil along the Middle East-China transportation route was solved by taking differential evolution algorithm (DEA) as the main part and four chromosome encoding, genome compression, variable interlock and near space-time priority encoding/decoding as the support sub-algorithms. While the constraint of supply-demand balance is satisfied, the scale of problems and the inferior solution space are reduced and ultimately the time of optimization is shortened effectively. When this algorithm was used to calculate the optimization of local ocean shipping scheme along the Middle East-China transportation route in one month, an appropriate feasible transportation scheme was obtained within 5 minutes and the transportation expense of the optimized scheme was 360 000 dollars less than that of the artificial scheme.